我呦呦呦又回来啦！
再来发一篇树形dp~
昨晚看的这道题，想了好久也不会（然后我就去睡觉了），今天突然明白是怎么回事了，一次A！（好感动）
简单分析一下，首先如果你想拿部分分，那是超级简单的，每一个点都dfs一遍咯，说实话真没啥技术含量。
考虑：假设我已经知道了一个点分别到它周围从1~k的距离的牛的数目的话，并且它的儿子节点我们已经求出这个节点以上（包括这个点）分别到它周围从1~k的距离的牛的数目，我就可以用父亲去更新儿子（以及简单的容斥原理）。
那为什么对于儿子节点，为什么我们不去考虑他父亲的父亲的值呢？
首先，对于这次dfs，一定是用父亲去更新儿子的，那么在儿子上面的点已经是不用更新的了，就考虑父亲节点的分支问题。那么这些点如果到儿子距离为 j ，它们到父亲的距离就一定为 j - 1 。但是我们加上的不仅仅是儿子下面的，也包括了它父亲上面的点，而这些点和已知的儿子上面（包括儿子）的部分有重合，那我们只需用一下可爱的容斥原理，减掉这部分就好 >\<，那么因为每一次只向上推进一个点，下面只要补足一个点作为用来更新的元素就可以了，每一次维护的一定都是最优解（实在不行：根节点本身就是最优；他的儿子只能用它更新，最优；他儿子的儿子只需要用到现有的最优解，就是它的父亲……），所以只需要用他它的父亲去更新。
那么提前处理的跑一遍dfs，用父亲更新儿子再跑一遍dfs，就大功告成啦！
另外有一点需要注意，循环的时候不一定大到小和小到大都可以，如果更新这个元素需要用到更小的还没有被更新过的原始解，那么只能从大到小枚举。
下面上代码：
#include<cstdio> #include<iostream> using namespace std; #define maxn 200005 int head[maxn],to[maxn],nxt[maxn],c[maxn],f[maxn][25]; int n,k,cnt; void add(int a,int b) { to[++cnt]=b; nxt[cnt]=head[a]; head[a]=cnt; } void dfs(int u,int fa) { f[u][0]=c[u]; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(v==fa) continue; dfs(v,u); for(int j=1;j<=k;j++) f[u][j]+=f[v][j-1]; } } void dp(int u,int fa) { for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(v==fa) continue; for(int j=k;j>=2;j--) f[v][j]-=f[v][j-2]; for(int j=k;j>=1;j--) f[v][j]+=f[u][j-1]; dp(v,u); } } int main() { scanf("%d%d",&n,&k); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } for(int i=1;i<=n;i++) scanf("%d",&c[i]); dfs(1,0); dp(1,0); for(int i=1;i<=n;i++) { int ans=0; for(int j=0;j<=k;j++) ans+=f[i][j]; printf("%d ",ans); } return 0; }