-
对于每个度数分别考虑，可以进行 dp，在状态中加入 \(0/1\) 表示是否保留与父亲的连边。
转移：
- 若 \(f_{v,0} + w \le f_{v,1}\)，则显然断掉更优。
- 否则，将 \(f_{v,0} + w - f_{v, 1}\) 作为一条边压入堆中，每次选出最小的断掉，直到仅剩下 \(lim\) 条边。
-
分析可得，若 \(deg_u \le lim\)，则 \(u\) 的每条边是互不影响的，也就是 \(v\) 只用考虑边权 \(w\)，而不关心 \(u\) 的子树内部情况。
这样将整个树分成了若干独立的森林，维护每个结点当前独立边的集合 \(s,t\) 分别为放弃的与保留的，并维护放弃的权值和。
-
每次只用考虑 \(deg_u > lim\) 的结点，这样总点数为 \(2n-2\)。
具体来说，然后对于每个结点，贪心保留前 \(lim\) 条边即可，这个可以用对顶堆来实现。
而对于每条边作为独立边本身只会被压入，弹出 \(1\) 次，每次求解注意只访问 \(deg > lim\) 的结点。
-
复杂度是均摊 \(O(n\log n)\) 的。
#include <bits/stdc++.h>
#include "roads.h"
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int, int> pii;
const int N = 3e5 + 10;
priority_queue <int> t[N];
priority_queue <int, vector <int>, greater <int> > s[N], q[N];
vector <pii> e[N];
int n, d[N], p[N], lim;
LL f[N][2], g[N], ans;
vector <LL> res;
bool vis[N];
bool cmp1_(pii u, pii v) {
return d[u.fi] > d[v.fi];
}
bool cmp2_(int u, int v) {
return d[u] > d[v];
}
void dfs_(int u) {
f[u][0] = f[u][1] = 0, vis[u] = 1;
while (s[u].size() > lim) {
int w = s[u].top();
g[u] += w, t[u].push(w);
s[u].pop();
}
while (t[u].size() && lim - s[u].size() >= 1) {
int w = t[u].top();
s[u].push(w), g[u] -= w;
t[u].pop();
}
f[u][0] = g[u];// 0 不保留， 1 保留
for (int v, w, i = 0; i < (int) e[u].size(); i++) {
v = e[u][i].fi, w = e[u][i].se;
if (d[v] <= lim)
break;
if (vis[v])
continue;
vis[v] = 1, dfs_(v), f[u][0] += min(f[v][0] + w, f[v][1]);
if (f[v][0] + w <= f[v][1])
continue;
q[u].push(f[v][0] + w - f[v][1]);
}
while (s[u].size() && q[u].size() && s[u].size() + q[u].size() > lim) {
int w1 = s[u].top(), w2 = q[u].top();
if (w1 >= w2)
f[u][0] += w2, q[u].pop();
else
f[u][0] += w1, g[u] += w1, t[u].push(w1), s[u].pop();
}
while (s[u].size() > lim) {
int w = s[u].top();
f[u][0] += w, g[u] += w, t[u].push(w), s[u].pop();
}
while (q[u].size() > lim) {
int w = q[u].top();
f[u][0] += w, q[u].pop();
}
f[u][1] = f[u][0];
while (s[u].size() && q[u].size() && s[u].size() + q[u].size() >= lim) {
int w1 = s[u].top(), w2 = q[u].top();
if (w1 >= w2)
f[u][1] += w2, q[u].pop();
else
f[u][1] += w1, g[u] += w1, t[u].push(w1), s[u].pop();
}
while (s[u].size() >= lim) {
int w = s[u].top();
f[u][1] += w, g[u] += w, t[u].push(w), s[u].pop();
}
while (q[u].size() >= lim) {
int w = q[u].top();
f[u][1] += w, q[u].pop();
}
while (!q[u].empty())
q[u].pop();
}
void del_(int u) {
for (int v, w, i = 0; i < (int) e[u].size(); i++) {
v = e[u][i].fi, w = e[u][i].se;
if (d[v] <= lim)
break;
if (t[v].size() && t[v].top() > w)
t[v].push(w), g[v] += w;
else
s[v].push(w);
}
}
vector <LL> minimum_closure_costs(int N, vector <int> U, vector <int> V, vector <int> W) {
n = N;
for (int u, v, w, i = 1; i < n; i++) {
u = U[i - 1] + 1, v = V[i - 1] + 1, w = W[i - 1], ans += w;
e[u].push_back(pii(v, w)), e[v].push_back(pii(u, w));
}
res.push_back(ans);
for (int i = 1; i <= n; i++)
d[i] = e[i].size(), p[i] = i;
for (int i = 1; i <= n; i++)
sort(e[i].begin(), e[i].end(), cmp1_);
sort(p + 1, p + n + 1, cmp2_);
for (int i = 1, j = n; i < n; i++) {
lim = i, ans = 0;
while (j && d[p[j]] <= lim)
del_(p[j--]);
for (int j = 1; j <= n; j++) {
if (d[p[j]] <= lim) {
for (int k = 1; k < j; k++)
vis[p[k]] = 0;
break;
}
if (!vis[p[j]])
dfs_(p[j]), ans += f[p[j]][0];
}
res.push_back(ans);
}
return res;
}