Description
Farmer John has noticed that his cows often move between nearby fields.Taking this into account, he wants to plant enough grass in each of his fields not only for the cows situated initially in that field, but also for cows visiting from nearby fields.
Specifically, FJ's farm consists of N fields (1 <= N <= 100,000), where some pairs of fields are connected with bi-directional trails (N-1 of them in total). FJ has designed the farm so that between any two fields i and j, there is a unique path made up of trails connecting between i and j. Field i is home to C(i) cows, although cows sometimes move to a different
field by crossing up to K trails (1 <= K <= 20).
FJ wants to plant enough grass in each field i to feed the maximum number of cows, M(i), that could possibly end up in that field -- that is, the number of cows that can potentially reach field i by following at most K trails. Given the structure of FJ's farm and the value of C(i) for each field i, please help FJ compute M(i) for every field i.
FJ发现他的牛经常跑到附近的草地去吃草，FJ准备给每个草地种足够的草供这个草地以及附近草地的奶牛来吃。FJ有N个草地(1<=N<=100000)，有N-1条双向道路连接这些草地，FJ精心设计了这些道路使每两个草地有且仅有一条简单路径连接。第i个草场有Ci头牛，有时候奶牛会走过K条道路到其他草地吃草。FJ想知道每个草场最多可能有的奶牛数量Mi，即所有走过K条道路后可能到达i的奶牛总数。
Input
* Line 1: Two space-separated integers, N and K.
* Lines 2..N: Each line contains two space-separated integers, i and j (1 <= i,j <= N) indicating that fields i and j are directly
connected by a trail.
* Lines N+1..2N: Line N+i contains the integer C(i). (0 <= C(i) <= 1000)
Output
* Lines 1..N: Line i should contain the value of M(i).
题目分析:
树形DP f[i][j]表示子树到i为j距离的和 g[i][j]表示整棵树到i为j的距离
首先： f[i][0]=c[x] f[i][j]=Σf[to[i]][j-1] 这个应该都没有问题
然后来做g[][] 初始化g[1][j]=f[1][j] (默认以点1为树的根) g[to[i]][0]=c[to[i]];
因为g[to[i]][j]是整棵树到to[i]距离为j 所以是子树+父树 因为子树就是f[to[i]][j]，已经求出来了 ，父树的点想要到达to[i],到达i的距离一定是j-1 所以g[to[i]][j]=f[to[i]][j]+g[i][j-1]
但是当J>=2时会多算子树里到to[i]距离为j-2的点 所以还要减一下
ans(i)=Σg[i][j] 0<=j<=k
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int f[100100][30];
int g[100100][30];
int n,k;
int head[1001000];
int to[1001000];
int next[1001000];
int tot;
int c[1001000];
void add(int x,int y)
{
next[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
void dfs(int x,int temp)
{
f[x][0]=c[x];
for(int i=head[x];i;i=next[i])
{
if(to[i]!=temp)
{
dfs(to[i],x);
for(int j=1;j<=k;j++)
f[x][j]+=f[to[i]][j-1];
}
}
}
void dfs2(int x,int temp)
{
for(int i=head[x];i;i=next[i])
{
if(to[i]!=temp)
{
g[to[i]][0]=c[to[i]];
for(int j=1;j<=k;j++)
{
g[to[i]][j]=f[to[i]][j]+g[x][j-1];
if(j>=2) g[to[i]][j]-=f[to[i]][j-2];
}
dfs2(to[i],x);
}
}
}
int ans;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
dfs(1,0);
for(int i=0;i<=k;i++)
g[1][i]=f[1][i];
dfs2(1,0);
for(int i=1;i<=n;i++)
{
ans=0;
for(int j=0;j<=k;j++)
ans+=g[i][j];
printf("%d\n",ans);
}
return 0;
}