题目
描述
\(n\) 个点的树，每条边有一个边权；
对于一个 \(X\) ，求删去一些边后使得每个点的度数 \(d_i\) 均不超过 \(X\) 的最小代价；
你需要依次输出 \(X=0 \to n-1\) 的答案；
范围
$ 1 \le n \le 250000 $
题解
-
考虑对于一个\(X\)怎么做，设 $ dp_{i,0/1} $ 表示 $ u $ 节点的子树，$ i $连向父亲的边是否被删且度数不超过 $ X $ 的最小代价。转移时将 \(dp_{v,1} + w(u,v) - dp_{v,0}\) 排序，小于 \(0\) 的优先选，再补到 $ d_{u} - X (-1) $ 个即可 。
复杂度 : \(O(n^2)\)
-
注意到 \(\sum_{i=0}^{n-1}\sum_{j=1}^{n} [d_j>i] = \sum_{i=1}^{n} d_{j} = 2n-2 = O(n)\) 。
升序考虑\(X\),当一个点的度数小于等于\(X\)的时候可以直接删去这个点并把这个点的贡献加入相邻的点中;
可以用一个支持删除的堆或者set实现。再执行同样的\(dp\)；
-
但是直接维护所有点仍是\(O(n^2log \ n )\)的，需要把复杂度降到只和当前保留的点有关。
注意到对于一个 $ u $ , $ d_{u}-X(-1) $ 在减小，维护堆中所有要选的$ d_{u}-X( -1 ) $个点的 $ sum $ ，这样子每次转移就只需要个新加儿子的\(dp\)值，然后调整堆的\(size\)即可，转移完后最后再还原；
这样子转移复杂度就只和度数\(>=X\)的点有关；
复杂度：\(O(n \log n)\) ;
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mk make_pair
#define ll long long
using namespace std;
const int N=250010;
int n,D,vis[N],d[N],nxt[N],st[N];
ll sum[N],ans,f[N][2];
typedef pair<int,int>pii;
vector<pii>g[N];
vector<int>vec[N];
int cnt;
bool cmp(const pii&a,const pii&b){
return d[a.fi]<d[b.fi];
}
struct data{
priority_queue<ll>A,B;
void push(ll x){
// cnt++;
A.push(x);
}
void del(ll x){
// cnt++;
B.push(x);
}
int top(){
while(!B.empty()&&A.top()==B.top())A.pop(),B.pop();
return A.top();
}
void pop(){
top();A.pop();
}
int size(){
return A.size()-B.size();
}
bool empty(){
return A.size()==B.size();
}
}q[N];
void update(int u){
vis[u]=1;
for(int i=0;i<g[u].size();++i){
int v=g[u][i].fi,w=g[u][i].se;
if(vis[v])continue;
q[v].push(w),sum[v]+=w;
}
}
void resize(int u,int num){
while(q[u].size()>num){
sum[u]-=q[u].top();
q[u].pop();
}
}
void resize(int u,int num,vector<ll>&add){
while(q[u].size()>num){
sum[u]-=q[u].top();
add.pb(q[u].top());
q[u].pop();
}
}
void dfs(int u,int F){
/*{
cnt++;
}*/
vis[u]=1;
int num=d[u]-D;
resize(u,num);
vector<ll>add,del;
ll all=0;
while(st[u]<g[u].size()&&d[g[u][st[u]].fi]<=D)st[u]++;
for(int i=st[u];i<g[u].size();++i){
int v=g[u][i].fi,w=g[u][i].se;
if(vis[v]||v==F)continue;
dfs(v,u);
if(f[v][1]+w<=f[v][0])num--,all+=f[v][1]+w;
else {
all+=f[v][0];
ll tmp=f[v][1]+w-f[v][0];
q[u].push(tmp),sum[u]+=tmp;
del.pb(tmp);
}
}
resize(u,max(0,num),add);
f[u][0]=all+sum[u];
resize(u,max(0,--num),add);
f[u][1]=all+sum[u];
for(auto x : add)q[u].push(x),sum[u]+=x;
for(auto x : del)q[u].del(x),sum[u]-=x;
}
int main(){
//freopen("F.in","r",stdin);
//freopen("F.out","w",stdout);
scanf("%d",&n);
for(int i=1,u,v,w;i<n;++i){
scanf("%d%d%d",&u,&v,&w);
g[u].pb(mk(v,w));
g[v].pb(mk(u,w));
d[u]++,d[v]++;
ans+=w;
}
for(int i=1;i<=n;++i){
vec[d[i]].pb(i);
sort(g[i].begin(),g[i].end(),cmp);
}
nxt[n]=n+1;
for(int i=n-1;i;--i){
if(vec[i+1].size())nxt[i]=i+1;
else nxt[i]=nxt[i+1];
}
printf("%I64d ",ans);
for(int i=1;i<n;++i){
for(auto j : vec[i])update(j);
ans=0;D=i;
for(int j=i+1;j<=n;j=nxt[j])
for(auto k : vec[j])if(!vis[k]){
dfs(k,0);ans+=f[k][0];
}
for(int j=i+1;j<=n;j=nxt[j])
for(auto k : vec[j]){
vis[k]=0;
}
printf("%I64d ",ans);
}
//cerr<<fixed<<setprecision(10)<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}