[CodeForces 1119F] Niyaz and Small Degrees（堆优化多次 DP） | 错题本

题目

[CodeForces 1119F] Niyaz and Small Degrees

分析

先考虑对于一个给定的 $x$ DP： $dp[u][0 / 1]$ 表示 $u$ 结点的度数为 $(x - 1) / x$，且其子树合法的删边代价。 $dp[u][0]$ 就意味着 $u$ 与其父亲的边保留， $dp[u][1]$ 意味着 $u$ 与其父亲的边删除。
设 $v$ 是 $u$ 的儿子， $w$ 是 $(u, v)$ 的边权，由于要求是度数 小于等于 $x$，所以贪心地想 $dp[v][1] + w \leq dp[v][0]$ 时肯定要删掉边 $(u, v)$，因为删掉不仅花费更少，还能让度数减少，因此此时 $dp[u][0 / 1] = dp[u][0 / 1] + dp[v][1] + w$ 否则我们先暂时保留该边： $dp[u][0 / 1] = dp[u][0 / 1] + dp[v][0]$ 做完一遍后可能点 $u$ 的度数还不符合要求，这时候就要将之前“暂时保留”的边删掉，于是删掉边 $(u, v)$ 的代价由 $dp[v][0]$ 变成了 $dp[v][1] + w$，变化量是 $dp[v][1] + w - dp[v][0]$。因此将所有暂时保留的边的 $dp[v][1] + w - dp[v][0]$ 放进一个优先队列中，取最小的 $m$ 个加进 $dp[u][0 / 1]$ 即可（ $m$ 是还要删的边数）。

注意到原图中度数小于等于 $x$ 的点实际上可以删掉。设某个度数小于等于 $x$ 的点为 $u$，它的某个度数大于 $x$ 的邻接点为 $v$， $u$ 对于 $v$ 来说就变成了一个叶子结点，于是只需要将边 $(u, v)$ 的权 $w$ 加入 $v$ 的优先队列中， $u$ 就可以被删掉了。进而我们从小到大枚举 $x$ 的话， $u$ 从此就彻底没用了。

按这个思路每次更新一下各个点的优先队列，再暴力 DP 一次，分析一下时间复杂度（ $d_i$ 表示 $i$ 号点的度） $\begin{aligned} &O\left(\left(\sum_{x = 0}^{n - 1} \sum_{i = 1}^n [d_i > x]\right)\log n\right) \\ = &O\left(\left(\sum_{i = 1}^n \sum_{x = 0}^{n - 1} [d_i > x]\right)\log n\right) \\ = &O\left(\left(\sum_{i = 1}^n d_i\right)\log n\right) \\ = &O((2n - 2)\log n) \\ = &O(n\log n) \end{aligned}$

代码

注意优先队列要支持删除，因为每次完了过后需要还原。
神仙卡常？ 注意注释那里的两行不加会 TLE。

#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>#define RI register inttypedef long long LL;
typedef std::pair<int, int> PII;const int MAXN = 250000;int N, Lim;
int Deg[MAXN + 5];
std::vector<PII> P;
std::vector<PII> G[MAXN + 5];bool Comp(PII i, PII j) {return Deg[i.first] > Deg[j.first];
}struct DeletableQueue {LL Sum; int Size;std::priority_queue<LL> Q, D;inline void Push(const LL &x) { Q.push(x), Size++, Sum += x; }inline void Delete(const LL &x) { D.push(x), Size--, Sum -= x; }inline LL Top() { while (!Q.empty() && !D.empty() && Q.top() == D.top()) Q.pop(), D.pop(); return Q.top(); }inline void Pop() { Sum -= Top(); Q.pop(); Size--; }
}H[MAXN + 5];int Vis[MAXN + 5];
LL Dp[MAXN + 5][2];void Dfs(int u, int fa) {Vis[u] = Lim;int cut = Deg[u] - Lim;Dp[u][0] = Dp[u][1] = 0;// 不加下面两句会 T 飞while (H[u].Size > cut)H[u].Pop();std::vector<LL> Add, Del;for (RI i = 0; i < int(G[u].size()); i++) {int v = G[u][i].first, w = G[u][i].second;if (Deg[v] <= Lim) break;if (v != fa) {Dfs(v, u);LL tmp = Dp[v][1] + w - Dp[v][0];if (tmp <= 0) {Dp[u][0] += Dp[v][1] + w;Dp[u][1] += Dp[v][1] + w;cut--;}else {Dp[u][0] += Dp[v][0];Dp[u][1] += Dp[v][0];H[u].Push(tmp);Del.push_back(tmp);}}}if (cut > 0) {while (H[u].Size > cut)Add.push_back(H[u].Top()), H[u].Pop();Dp[u][0] += H[u].Sum;while (H[u].Size > cut - 1)Add.push_back(H[u].Top()), H[u].Pop();Dp[u][1] += H[u].Sum;}for (RI i = 0; i < int(Add.size()); i++)H[u].Push(Add[i]);for (RI i = 0; i < int(Del.size()); i++)H[u].Delete(Del[i]);
}int main() {scanf("%d", &N);LL Ans = 0;for (RI i = 1; i < N; i++) {int u, v, w; scanf("%d%d%d", &u, &v, &w);Deg[u]++, Deg[v]++;G[u].push_back(std::make_pair(v, w));G[v].push_back(std::make_pair(u, w));Ans += w;}printf("%lld", Ans);for (RI i = 1; i <= N; i++) {P.push_back(std::make_pair(Deg[i], i));std::sort(G[i].begin(), G[i].end(), Comp);}std::sort(P.begin(), P.end());RI cur = 0;for (Lim = 1; Lim < N; Lim++) {while (cur < N && P[cur].first == Lim) {int u = P[cur].second;for (RI i = 0; i < int(G[u].size()); i++) {int v = G[u][i].first, w = G[u][i].second;if (Deg[v] <= Lim) break;H[v].Push(w);}cur++;}Ans = 0;for (RI i = cur; i < N; i++) {int u = P[i].second;if (Vis[u] != Lim) {Dfs(u, 0);Ans += Dp[u][0];}}printf(" %lld", Ans);}return 0;
}