拿到 \(S(i) = \sum\limits_{j = 1} ^ n \operatorname{dist}(i, j) ^ k\)。
首先我们啥也做不了，只能根据 Stirling 数的那堆柿子硬拆开，有 \(m ^ n = \sum\limits_{i = 0} ^ m {n \brace i} i! \binom{m}{i} = \sum\limits_{i = 0} ^ n {n \brace i} i! \binom{m}{i}\)。代入：
\[S(i) = \sum\limits_{j = 1} ^ n \sum\limits_{l = 0} ^ k {k \brace l} l! \binom{\operatorname{dist}(i, j)}{l} \]交换求和顺序：
\[S(i) = \sum\limits_{l = 0} ^ k {k \brace l} l! \sum\limits_{j = 1} ^ n \binom{\operatorname{dist}(i, j)}{l} \]那么重点就是计算 \(\sum\limits_{j = 1} ^ n \binom{\operatorname{dist}(i, j)}{l}\)。而我们知道 \(\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}\)。考虑直接设 \(f_{u, i}\) 表示 \(u\) 的子树中的所有 \(v\) 的 \(\sum\limits_{j = 1} ^ n \binom{\operatorname{dist}(u, v)}{i}\)。则有 \(f_{u, i} = f_{v, i} + f_{v, i - 1}\)。
然后 \(n \leq 5 \times 10 ^ 4\)，需要换根。这里是一种 up and down 的换根，适用于根变化，统计全局。具体思路就是：计算好固定某一点为根的 dp 值（相当于得到了以该点为根的答案值），然后减去其子树的贡献，再反过来去更新子树的点（作为子树的点的一个子树的点），如此递归。要注意了！自己换根能力菜的一批
标签：dist,limits,int,sum,up,down,小题,binom,operatorname From： https://www.cnblogs.com/liuzimingc/p/18116288/up-and-down