本文共 1587 字，大约阅读时间需要 5 分钟。

$定义down[i][j]为i为根的子树往下j级儿子的点权和$

$定义dp[i][j]表示i在整棵树中距离j的点权和$

$那么怎么求dp[i][j]?$

$显然down[i][j]是dp[i][j]的一部分,现在还需要在i上面距离j的$

$u是i的父亲,那不就是dp[u][j-1]嘛?$

$但是多算了,多算了down[v][j-2]$

#include 
   
    using namespace std;#define int long longconst int maxn=2e5+10;int n,c[maxn],ans=1e18,sumn,k;struct edge{	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){	d[++cnt]=(edge){v,head[u]},head[u]=cnt;}int down[maxn][21],dp[maxn][21];void dfs1(int u,int fa){	down[u][0]=c[u];	for(int i=head[u];i;i=d[i].nxt )	{		int v=d[i].to;		if( v==fa )	continue;		dfs1(v,u);		for(int j=1;j<=k;j++)			down[u][j]+=down[v][j-1];	}}void DP(int u,int fa){	dp[u][0]=c[u];	for(int i=head[u];i;i=d[i].nxt )	{		int v=d[i].to;		if( v==fa )	continue;		for(int j=1;j<=k;j++)	dp[v][j]=dp[u][j-1]+down[v][j];		for(int j=2;j<=k;j++)	dp[v][j]-=down[v][j-2];		DP(v,u);	}}signed main(){	cin >> n >> k;	for(int i=1;i
    
     > l >> r;		add(l,r);	add(r,l);	}	for(int i=1;i<=n;i++)	cin >> c[i];	dfs1(1,0);	for(int i=1;i<=n;i++)	for(int x=0;x<=k;x++)		dp[i][x]=down[i][x];	DP(1,0);	for(int i=1;i<=n;i++)	{		for(int j=1;j<=k;j++)	dp[i][j]+=dp[i][j-1];		cout << dp[i][k] << '\n';	}}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108249869 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！