换根法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
	int u,v;
};
int n,k,res,b[N],c[N],dp[N];
int size[N][21],f[N],fa[N],s[N];
vector<int> p[N];
void add(int u,int v)
{
	p[u].push_back(v);
}
void dfs1(int u,int fath)
{
	int i,v;
	for(i=0;i<p[u].size();i++)
	{
		v=p[u][i];
		if(v==fath) continue;
		dfs1(v,u);
		fa[v]=u;
	}
}
void dfs2(int u,int y)
{
	int i,v;
	size[res][y]+=s[u];
	if(y==k+1) {
		return ;
	}
	for(i=0;i<p[u].size();i++)
	{
		v=p[u][i];
		if(v==fa[u]) continue;
		dfs2(v,y+1);
	}
}
void dfs3(int u)
{
	int i,v;
	f[u]=s[u];
	for(i=0;i<p[u].size();i++)
	{
		v=p[u][i];
		if(v==fa[u]) continue;
		dfs3(v);
		f[u]+=(f[v]-size[v][k]);
	}
}
void dfs4(int u)
{
	int i,v;
	int a;
	a=f[u];
	for(i=0;i<=k;i++){
		b[i]=size[u][i];
		c[i]=size[fa[u]][i];
	}
	if(u>1){
		f[u]=f[u]+(f[fa[u]]-(f[u]-size[u][k])-(size[fa[u]][k]-size[u][k-1]));
		dp[u]=f[u];
		for(i=1;i<=k;i++)
			size[fa[u]][i]-=b[i-1];
		size[u][1]+=c[0];
		for(i=2;i<=k;i++)
			size[u][i]+=c[i-1]-b[i-2];
	}
	for(i=0;i<p[u].size();i++){
		v=p[u][i];
		if(v==fa[u]) continue;
		dfs4(v);
	}
	f[u]=a;
	for(i=0;i<=k;i++){
		size[u][i]=b[i];
		size[fa[u]][i]=c[i];
	}
}
int main()
{
	int i;
	int u,v;
	cin>>n>>k;
	for(i=1;i<n;i++)
	{
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(i=1;i<=n;i++)
	cin>>s[i];
	dfs1(1,0);
	for(i=1;i<=n;i++)
	{
		res=i;
		dfs2(i,0);
	}
	dfs3(1);
	dfs4(1);
	dp[1]=f[1];
	for(i=1;i<=n;i++)
	cout<<dp[i]<<endl;
 	return 0;
}