自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:06:23，当前版本为作者最后更新于2024-12-10 21:19:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

奶龙题，但是为什么想了半个小时？？？

如果不换根，答案就是将树进行长链剖分后选前 $k$ 大。

考虑换根的过程中直接维护所有的长链。发现从 $u \to v$，唯一的变化就是将某个数减去 $w$，再将另外一个数加上 $w$，求前 $k$ 大。

这个问题咋做都行，随便写了一个线段树。（显然可以也 multiset）

刚开始把子树内、子树外的长链分开考虑了，然后发现必须可持久化……

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=4e5+10;
int n,k,mx_in[MAXN],mx_out[MAXN],lsh[MAXN],tot,ans[MAXN];
namespace DS {
	int cnt[MAXN<<2],sum[MAXN<<2];
	#define lson (k<<1)
	#define rson (k<<1|1)
	#define mid (l+r>>1)
	void update(int k,int l,int r,int pos,int dcnt,int dsum) {
		cnt[k]+=dcnt,sum[k]+=dsum;
		if(l==r) return ;
		if(pos<=mid) update(lson,l,mid,pos,dcnt,dsum);
		else update(rson,mid+1,r,pos,dcnt,dsum);
		return ;
	}
	int calc(int k,int l,int r,int c) {
		if(c>=cnt[k]) return sum[k];
		if(l==r) return lsh[l]*c;
		if(c<=cnt[rson]) return calc(rson,mid+1,r,c);
		return sum[rson]+calc(lson,l,mid,c-cnt[rson]);
	}
};
vector<pair<int,int>> G[MAXN],T[MAXN];
void dfs1(int u,int f) {
	for(auto pr:G[u]) {
		int v=pr.first,w=pr.second;
		if(v==f) continue ;
		dfs1(v,u),mx_in[u]=max(mx_in[u],mx_in[v]+w),T[u].push_back(pr);
	}
	return ;
}
void dfs2(int u,int f) {
	int mx=mx_out[u];
	for(auto pr:T[u]) {
		int v=pr.first,w=pr.second;
		mx_out[v]=max(mx_out[v],mx+w),mx=max(mx,mx_in[v]+w);
	}
	reverse(T[u].begin(),T[u].end()),mx=mx_out[u];
	for(auto pr:T[u]) {
		int v=pr.first,w=pr.second;
		mx_out[v]=max(mx_out[v],mx+w),mx=max(mx,mx_in[v]+w);
		lsh[++tot]=mx_in[v]+w,lsh[++tot]=mx_out[v]-w,lsh[++tot]=mx_in[v],lsh[++tot]=mx_out[v];
	}
	for(auto pr:T[u]) dfs2(pr.first,u);
	return ;
}
int find(int k) {return lower_bound(lsh+1,lsh+tot+1,k)-lsh;}
void dfs3(int u,int f) {
	int flg=0;
	for(auto pr:T[u]) {
		int v=pr.first,w=pr.second;
		if(mx_in[v]+w!=mx_in[u]||flg) DS::update(1,1,tot,find(mx_in[v]+w),1,mx_in[v]+w);
		else flg=1;
	}
	for(auto pr:T[u]) dfs3(pr.first,u);
	return ;
}
void dfs4(int u,int f) {
	ans[u]=DS::calc(1,1,tot,k);
	for(auto pr:T[u]) {
		int v=pr.first,w=pr.second;
		int del1=find(mx_in[v]+w),del2=find(mx_out[v]-w);
		int add1=find(mx_in[v]),add2=find(mx_out[v]);
		DS::update(1,1,tot,del1,-1,-(mx_in[v]+w));	
		DS::update(1,1,tot,del2,-1,-(mx_out[v]-w));
		DS::update(1,1,tot,add1,1,mx_in[v]);
		DS::update(1,1,tot,add2,1,mx_out[v]);
		dfs4(v,u);
		DS::update(1,1,tot,del1,1,mx_in[v]+w);	
		DS::update(1,1,tot,del2,1,mx_out[v]-w);
		DS::update(1,1,tot,add1,-1,-mx_in[v]);
		DS::update(1,1,tot,add2,-1,-mx_out[v]);
	}
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	ffor(i,1,n-1) {int u,v,w;cin>>u>>v>>w,G[u].push_back({v,w}),G[v].push_back({u,w});}
	dfs1(1,0),dfs2(1,0);
	sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1;
	DS::update(1,1,n,find(mx_in[1]),1,mx_in[1]),dfs3(1,0);
	dfs4(1,0);
	ffor(i,1,n) cout<<ans[i]<<'\n';
	return 0;
}