(mathcal{Description})
Link.
给定一棵 (n) 个结点的树，边有边权，对于每个整数 (xin[0,n))，求出最少的删边代价使得任意结点度数不超过 (x)。
(nle2.5 imes10^5)。
(mathcal{Solution})
从单个询问入手，设此时 (x) 为常数，就有一个简单的树上 DP。令 (f(u,0/1)) 表示 (u) 点与父亲的边不断 / 断时，(u) 子树内的最小代价。以 (f(u,0)) 为例，设 (v) 是 (u) 的儿子，转移相当于强制选择至少 (max{0,d_u-x}) 个 (f(v,1)) 进行转移。先特判掉 (f(v,1)+operatorname{cost}(u,v)le f(v,0)) 的 (v)，此时用 (f(v,1)+operatorname{cost}(u,v)) 的代价断边显然更优。此后，先仅用 ((v,0)) 转移，把 (f(v,1)+operatorname{cost}(u,v)-f(v,0)) 压入大根堆。保留堆最后 (max{0,d_u-x}) 个元素并加入贡献就行啦。
接下来，按 (x) 从 (0) 到 (n-1) 的顺序考虑询问。可以发现，在 (x) 增大的过程中，某些点的度数不超过 (x)，那么 (x) 对这些点就再也没有限制了。那么强行把这个点拉到叶子，将它的 DP 信息压入邻接点的堆，再暴力跑 DP 就解决了。
复杂度 (mathcal O(nlog n))。
(mathcal{Code})
#pragma GCC optimize( 2 )
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
const int MAXN = 2.5e5;
int n, ecnt, head[MAXN + 5], deg[MAXN + 5], vis[MAXN + 5];
LL f[MAXN + 5][2];
std::pair<int, int> order[MAXN + 5];
bool kill[MAXN + 5];
inline char fgc () {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && ( q = buf + fread ( p = buf, 1, 1 << 17, stdin ), p == q ) ? EOF : *p ++;
}
inline int rint () {
int x = 0; char d = fgc ();
for ( ; d < '0' || '9' < d; d = fgc () );
for ( ; '0' <= d && d <= '9'; d = fgc () ) x = x * 10 + ( d ^ '0' );
return x;
}
inline void wint ( const LL x ) {
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
std::vector<LL> pmem, rmem;
std::vector<std::pair<int, int> > gr[MAXN + 5];
struct RemovableHeap {
int siz; LL sum;
std::priority_queue<LL> ele, rem;
RemovableHeap (): siz ( 0 ), sum ( 0 ) {}
inline void snap () { pmem.clear (), rmem.clear (); }
inline void nspush ( const LL x ) { ++ siz, sum += x, ele.push ( x ); }
inline void nspop ( const LL x ) { -- siz, sum -= x, rem.push ( x ); }
inline void nspop () { -- siz, sum -= top (), ele.pop (); }
inline void push ( const LL x ) { nspush ( x ), pmem.push_back ( x ); }
inline void pop ( const LL x ) { nspop ( x ), rmem.push_back ( x ); }
inline void pop () { -- siz, sum -= top (), rmem.push_back ( top () ), ele.pop (); }
inline int size () { return siz; }
inline LL top () {
for ( ; ! ele.empty () && ! rem.empty () && ele.top () == rem.top (); ele.pop (), rem.pop () );
return ele.top ();
}
inline void recov () {
for ( LL p: pmem ) nspop ( p );
for ( LL r: rmem ) nspush ( r );
pmem.clear (), rmem.clear ();
}
} heap[MAXN + 5];
inline void solve ( const int u, const int x, const int fa ) {
vis[u] = x; int wait = deg[u] - x;
for ( ; heap[u].size () > wait; heap[u].nspop () );
for ( auto v: gr[u] ) {
if ( v.first == fa ) continue;
if ( deg[v.first] <= x ) break;
solve ( v.first, x, u );
}
heap[u].snap ();
LL bas = 0;
for ( auto v: gr[u] ) {
if ( v.first == fa ) continue;
if ( deg[v.first] <= x ) break;
LL dt = f[v.first][1] + v.second - f[v.first][0];
if ( dt <= 0 ) { -- wait, bas += f[v.first][1] + v.second; continue; }
bas += f[v.first][0], heap[u].push ( dt );
}
for ( ; heap[u].size () && heap[u].size () > wait; heap[u].pop () );
f[u][0] = bas + heap[u].sum;
for ( ; heap[u].size () && heap[u].size () > wait - 1; heap[u].pop () );
f[u][1] = bas + heap[u].sum;
heap[u].recov ();
}
int main () {
n = rint ();
LL ws = 0;
for ( int i = 1, u, v, w; i < n; ++ i ) {
u = rint (), v = rint (), w = rint ();
++ deg[u], ++ deg[v], ws += w;
gr[u].push_back ( { v, w } );
gr[v].push_back ( { u, w } );
}
wint ( ws );
for ( int i = 1; i <= n; ++ i ) {
order[i] = { deg[i], i };
sort ( gr[i].begin (), gr[i].end (),
[]( const std::pair<int, int> a, const std::pair<int, int> b ) {
return deg[a.first] > deg[b.first];
}
);
}
std::sort ( order + 1, order + n + 1 );
for ( int x = 1, dis = 1; x < n; ++ x ) {
for ( int u; dis <= n && order[dis].first == x; ++ dis ) {
kill[u = order[dis].second] = true;
for ( auto v: gr[u] ) {
if ( deg[v.first] <= x ) break;
heap[v.first].nspush ( v.second );
}
}
LL ans = 0;
for ( int i = dis, u; i <= n; ++ i ) {
if ( vis[u = order[i].second] ^ x ) {
solve ( u, x, 0 );
ans += f[u][0];
}
}
putchar ( ' ' ), wint ( ans );
}
putchar ( '
' );
return 0;
}