CF161D

CF161D

点分/长链剖分/dsu 随便过。

但注意到数据范围不强，考虑 $O(nk)$ 的复杂度，可以树形DP。设 $f_{u,i}$ 表示以 $u$ 为根，子树中离 $u$ 路径长度为 $i$ 的点数。

统计答案时考虑每个的贡献是 $f_{u,j}\times f_{v,k-i-j}$（$0\le j<k$）。然后再转移 $f_{u,j+1}=\sum_{v\in u}f_{v,j}$。

这样的正确性在于，每次统计答案时都是新的和当前的统计，再把新的更新，不重不漏，有点像枚举两点时 $j$ 从 $i+1$ 开始枚举。第一遍没过就是这里没考虑好，shaber 了。

void dfs(int u,int fa){
    f[u][0]=1;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        for(int i=0;i<k;++i) ans+=(f[u][i]*f[v][k-i-1]);
        for(int i=0;i<k;++i) f[u][i+1]+=f[v][i];
    }
}