看题以为自己会了，写代码的时候发现有细节没考虑清楚，复杂度写挂了以为被卡常了，调用并查集函数还手残打错了，浪费大半个下午。NOI 之后属于越训越菜了 QwQ。
回到这个题，首先这个题当 \(i\) 固定时做法是显然的，我们自底向上考虑，每次一定是 ban 掉连向当前最长链最大子树的 \(i\) 条边。
发现只有当 \(deg_i>x\) 时一个点才有考虑价值，而 \(\sum_{x=0}^{n-1} \sum_u [deg_u>x]=\sum_u deg_u\) 是 \(O(n)\) 级别的。建出虚树，然后每个点相当于删除若干个边权，加入若干个新边权，求第 \(k\) 大。可以使用平衡树维护。做完了，复杂度 \(O(n\log n)\)。
如果我直接写虚树+平衡树，我就不用浪费这个下午了，但是我脑子一抽突然不想写十级算法。所以我们可以考虑用并查集维护当前还存在的 \(deg_u>x\) 的点，再开一颗并查集，按照 dfs 序倒序遍历，每次删去在当前所有点子树的关键点，就可以实现跟虚树同样的功能且免去了常数大的递归，但是复杂度其实是带一个小 \(\log n\) 或 \(\alpha(n)\) 的。
平衡树也好难写，每次加入删除之后还要删除加入回去常数大飞，我们考虑用常数更小的算法。注意到题目对于一个已经准备好的数组形如删除若干个，加入若干个，然后还要回退回去。我们考虑经典的用堆维护第 \(k\) 大，所以我们只需要开一个小根堆存储最大的 \(k\) 个。
使用可删堆不够优美，因为还是要回退回去。我们考虑用两个堆结构拼成一个堆，把一个点下面的所有边排序一下，取后面若干个直接作为其中一个堆，由于原本存在的边只会被删，所以这里就是直接用一个指针就可以实现弹堆了。然后你就可以做到洛谷最快了。
我是在这里干些什么啊 \yun。
#include <queue>
#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#define fi first
#define se second
using namespace std;
int read(){ /* reading... */ }
const int N=200003;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
inline void chmx(ll &x,ll v){if(x<v) x=v;}
inline void chmn(ll &x,ll v){if(x>v) x=v;}
int n;
vector<pii> adj[N],tr[N],vec[N];
int dfn[N],o[N],sz[N],ps[N],num;
void dfs(int u,int fa){
o[dfn[u]=++num]=u;
sz[u]=1;
for(auto [v,w]:adj[u]) if(v^fa){
dfs(v,u);
tr[u].emplace_back(w,v);
vec[u].emplace_back(v,w);
sz[u]+=sz[v];
}
sort(tr[u].begin(),tr[u].end());
int tt=0;
for(auto [w,v]:tr[u]) ps[v]=tt++;
}
int f[N],g[N];
bool del[N];
int rt(int x){
if(f[x]==x) return x;
return f[x]=rt(f[x]);
}
int go(int x){
if(g[x]==x) return x;
return g[x]=go(g[x]);
}
int stk[N],tp;
int que[N],tl;
ll dp[N],ed[N];
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read(),w=read();
adj[u].emplace_back(v,w);
adj[v].emplace_back(u,w);
}
dfs(1,0);
for(int i=n;i;--i) stk[++tp]=o[i];
for(int i=1;i<=n+1;++i) f[i]=i;
g[n+1]=n+1;
int cnt=0;
for(int x=0;x<n;++x){
ll res=0;
for(int i=1;i<=tp;++i) g[dfn[stk[i]]]=dfn[stk[i]];
for(int i=1;i<=tp;++i){
int u=stk[i];
int ss=tr[u].size();
if(ss<=x){f[dfn[u]]=dfn[u]+1;continue;}
g[dfn[u]]=dfn[u];
vector<pii> tmp;
que[++tl]=u;
int p=ss-x-1;
ll tdp=0;
priority_queue<ll,vector<ll>,greater<ll>> pq;
for(auto [v,w]:vec[u]){
ed[v]=0;bool fl=0;
for(int t=go(rt(dfn[v]));t<dfn[v]+sz[v];t=go(t)) chmx(ed[v],dp[o[t]]+w),fl=1,g[t]=rt(t+1),chmx(tdp,dp[o[t]]);
if(fl){
tmp.emplace_back(v,w);
del[v]=1;pq.emplace(ed[v]);
if(ps[v]<p){
if(!pq.empty()&&(p==ss||tr[u][p].fi>pq.top())) pq.pop();
else ++p;
}
while(p<ss&&del[tr[u][p].se]) ++p;
}
}
dp[u]=1e18;
if(p<ss) chmn(dp[u],tr[u][p].fi);
if(!pq.empty()) chmn(dp[u],pq.top());
vec[u].swap(tmp);
for(auto [v,w]:vec[u]) del[v]=0;
chmx(dp[u],tdp);
chmx(res,dp[u]);
}
tp=tl;tl=0;
for(int i=1;i<=tp;++i) stk[i]=que[i];
printf("%lld ",res);
}
putchar('\n');
return 0;
}