题意
给定一棵树，对于每个节点 \(u\)，求 \(\sum\limits_{v = 1}^{n} \operatorname{dist}(u, v) ^k\)，其中 \(\operatorname{dist(u, v)}\) 表示 \(u, v\) 两点间的距离。
题解
首先考虑化简算式中的 \(k\) 次幂，考虑使用斯特林数的性质：
\[n^k = \sum\limits_{i = 0}^{k} {n \choose i} \times i! \times {k \brace i}
\]
所以可以化简原式
\[\begin{aligned}
S(u) =& \sum\limits_{v = 1}^{n} \operatorname{dist}(u, v)^k \\
=& \sum\limits_{v = 1}^{n} \sum\limits_{i = 0}^{k} {\operatorname{dist}(u, v) \choose i} \times i! \times {k \brace i} \\
=& \sum\limits_{i = 0}^{k} i! \times {k \brace i} \sum\limits_{v = 1}^{n} {\operatorname{dist}(u, v) \choose i}
\end{aligned}\]
设 \(\displaystyle f(u, i) = \sum\limits_{v = 1}^{n}{\operatorname{dist}(u, v) \choose i}\)，那么我们可以得到
\[S(u) = \sum\limits_{i = 0}^{k} i! \times {k \brace i} \times f(u, i)
\]
下面考虑如何求出 \(\displaystyle f(u, i)\)，首先考虑子树的贡献，设 \(\displaystyle dp(u, i) = \sum\limits_{v \in \operatorname{subtree_u}}{\operatorname{dist}(u, v) \choose i}\)，发现对于 \(\displaystyle y \in \operatorname{\operatorname{son_u}}, v \in \operatorname{subtree_u}\)， 有 \(\operatorname{dist}(u, v) = \operatorname{dist}(y, v) + 1\)，考虑转移式
\[\begin{aligned}
dp(u, i) =& \sum\limits_{v \in \operatorname{subtree_u}}{\operatorname{dist}(u, v) \choose i} \\
=& \sum\limits_{y \in \operatorname{son_x}} \sum\limits_{v \in \operatorname{subtree_y}} {\operatorname{dist}(u, v) \choose i} \\
=& \sum\limits_{y \in \operatorname{son_x}} \sum\limits_{v \in \operatorname{subtree_y}} {\operatorname{dist}(y, v) + 1 \choose i} \\
=& \sum\limits_{y \in \operatorname{son_x}} \sum\limits_{v \in \operatorname{subtree_y}} {\operatorname{dist}(y, v) \choose i} + {\operatorname{dist}(y, v) \choose i - 1} \\
=& \sum\limits_{y \in \operatorname{son_x}} dp(y, i) + dp(y, i - 1)
\end{aligned}\]
上述的推导使用了杨辉三角的递推式：
\[{n \choose m} = {n - 1 \choose m} + {n - 1 \choose m - 1}
\]
这样我们就可以从叶子节点向上更新出每个节点的 \(dp(u, i)\) 值了。接下来考虑求出 \(f(u, i)\) 的值，记 \(fa\) 为 \(u\) 的父亲节点，发现对于 \(\displaystyle v \in \operatorname{subtree_u}\)，有 \(\operatorname{dist}(u, v) = \operatorname{dist}(fa, v) - 1\)；对于 \(v \notin \operatorname{subtree_u}\)，有 \(\operatorname{dist}(u, v) = \operatorname{dist}(fa, v) + 1\)，考虑转移式
\[\begin{aligned}
f(u, i) =& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(u, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(u, v) \choose i} \\
=& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) + 1 \choose i} \\
=& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} + \\
&\sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} \\
=& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} - \\
&\sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} \\
=& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} + \\
&\sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} \\
=& f(fa, i) + f(fa, i - 1) - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} \\
=& f(fa, i) + f(fa, i - 1) - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}
(fa, v) - 1 \choose i - 1} - \\
&\sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 2} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} \\
=& f(fa, i) + f(fa, i - 1) - 2f(u, i - 1) - f(u, i - 2)
\end{aligned}\]
上述推导中均运用了杨辉三角递推式。利用推导出的转移式我们可以以 \(\mathcal{O}(nk)\) 的复杂度处理出 \(f(u, i)\) 的值，同时我们可以以 \(\mathcal{O}(k^2)\) 的复杂度预处理出需要的斯特林数，再代入 \(S(u)\) 的表达式即可求出答案，总复杂度为 \(\mathcal{O}(nk + k^2)\)。
Code
出于篇幅考虑，代码放在云剪切板中。