前言

没啥可说的。

题目大意

给你一棵 $n$ 个点的树，点带权，对于每个节点求出距离它不超过 $k$ 的所有结点权值和 $m_i$。

思路

首先暴力做法肯定直接 $O(n^2)$ 直接做，但是一看数据范围就喜提TLE。考虑树上 dp。

通常树上 dp 都配合着 dfs 来做，本题也不例外。

首先我们定义 $dp[u][K]$ 为已 $u$ 为根结点向周围遍历 $K$ 距离的结点权值之和。那么开始可以想到这个方程：

$dp[u][K]=\Sigma dp[v][K-1]$

但是这对吗，这不对。因为这只是从子孩子得来的结果，本题讨厌就讨厌在可以从父亲也得来结果，所以虽然是树性结构但不是传统上的树。所以可以再用一下我为人人 的思路。

$dp[v][K]=\Sigma dp[u][K-1]$

但是这样就1很明显会有重复部分，也就是第一个 dfs 的子树部分。所以要减去 $dp[v][K-2]$。

之后注意一下，第二个循环是要倒推的，因为减去的是原来第一 个 dfs 的子树部分，正着推就跟之前加的父亲算重了。然后第二个的 dfs 要放到循环结束，因为要先更新完当前节点才可以从当前结点更新子树。第一个的要放到之前，与第二个 dfs 相反，要先得到子树的结果才可以更新当前结点。

代码

#include <iostream>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
const ll INF=ll(1e30);

struct edge{
    ll to,nxt;
}e[MAXN];
ll head[MAXN],tot;
void add(ll u,ll v){
    e[++tot].nxt= head[u];
    e[tot].to=v;
    head[u]=tot;
}
ll n,k;
ll dp[MAXN][25];
void dfs1(ll u,ll f){
    for (ll i = head[u]; i ; i=e[i].nxt) {
        ll v=e[i].to;
        if(v!=f){
            dfs1(v,u);
            for (int j = 1; j <=k ; ++j) {
                dp[u][j]+=dp[v][j-1];
            }
        }
    }
}
void dfs2(ll u,ll f){
    for (ll i = head[u]; i ; i=e[i].nxt) {
        ll v=e[i].to;
        if(v!=f){
            for (ll j = k; j >=2 ; --j) {
                dp[v][j]+=dp[u][j-1]-dp[v][j-2];
            }
            dp[v][1]+=dp[u][0];
            dfs2(v,u);
        }
    }
}
int main() {
    scanf("%lld%lld",&n,&k);
    for (int i = 1; i <=n-1 ; ++i) {
        ll u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&dp[i][0]);
    }
    dfs1(1,0);
    dfs2(1,0);
    for (int i = 1; i <=n ; ++i) {
        ll ans=0;
        for (int j = 0; j <=k ; ++j) {
            ans+=dp[i][j];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

总结

本题更加加深了对树形 dp 的概念，同时如果题目又要跟父结点联系也要跟子结点发生联系的就可以跟本题一样分成两个 dfs 来写。之后记得在 dfs 中间别算重了，画个图判一下容斥。