https://www.luogu.com.cn/problem/P4827
看到 n \leq 5\times 10^4, k \leq 150 容易想到是 \Theta (nk) 或者加一个 \log 的复杂度。
首先考虑慢一些的方法：如果我们知道了某个点 u 的答案，想要间接取得 u 的某个儿子 v 的答案；对于 d(u,v)=1 和 d(v, v') v' 是 v 中任意一点的 \rm dis 全部减小 1 对于 u 到 v 子树外任意一点距离 d(u, u') 增加 1
设原答案为 \begin{aligned}\sum d^k \end{aligned} ，这时答案变为 \begin{aligned}\sum (d-1)^k +\sum (d + 1)^k\end{aligned} , 又因为有 \begin{aligned}\sum (d + \theta )^k=\sum_{j=0}^k\binom{k}{j}d^j \end{aligned} 所以我们只需要维护每个点 d^j 的答案即可。设 f_{u,j} 表示 u 为根时子树中任意距离 d 的答案 \begin{aligned}\sum d^j\end{aligned} , g_{u,j} 表示 u 为根时子树外任意距离 d 的答案 ，可以知道每次从儿子转移时候距离 +1 并新生成了和儿子的距离，转移为 \begin{aligned}f_{u,j}=\sum_v1+\sum_{q=0}^j\binom{j}{q}f_{v,q}\end{aligned} ；对于子树外，考虑容斥掉这个子树里的贡献，转移为 \begin{aligned}g_{u,j}=1+\sum_{q=0}^j (f_{fa}+g_{fa}-1-\sum_{x=0}^q \binom{q}{x}f_{u,x})\binom{j}{q}\end{aligned} ，其中外面的 1 为 (u,fa) 间新增的长度为 1 的路径，里面的 1 为 (u, fa) 间原有的长度为 1 的路径。那么 u 为根的答案就是 f_{u,k}+g_{u,k} 。
易错点是路径的贡献问题： f 的定义是子树内所有路径，不包括到自身；某个子树 v 的贡献是 f_v 向父亲方向迭代一次后加上 (v, u) 的这条长度为 1 的路径，因为原来的迭代中不包含这条路径 (可以从获取 f 的转移中发现)
这样转移复杂度事 O (nk^2)
正解： 看到k次幂考虑转斯特林数然后类似二项式系数直接递推合并，复杂度 O(nk)