其中 $f_x$ 为以结点 $x$ 为根的子树对应的哈希值。

$size_{x}$ 表示以结点 $x$ 为根的子树大小。

$son_{x,i}$ 表示 $x$ 所有子结点之一（不用排序）。

$prime(i)$ 表示第 $i$ 个质数。

参考博客 树hash

题面

给定一棵无根树，对每个点 $i$，求 $S(u)=\sum_{i=1}^n dis(u,i)^k$，$dis(u,i)$ 表示树上路径长度。

其中 $3\le n \le 5\cdot 10^4, 1\le k \le 200$。

分析

做法一

斯特林数展开。

其中 $n^{\underline m}=P(n,m)$ 表示 $n$ 的 $m$ 次下降幂。

记 $dp(u,i)$ 表示 $u$ 的子树下所有点对 $i$ 次下降幂的贡献，即 $\sum_{v \in subtree(u)} dis(u,v)^{\underline i}$。

转移就是考虑恒等式 $n^{\underline m}=(n-1)^{\underline m}+m\cdot n^{\underline m-1}$，做两遍 up and down 的树形 dp 即可。

做法二

$dp(u,i)$ 直接维护出 $u$ 的子树内所有点到 $u$ 的距离的 $i$ 次方之和。

转移就是考虑 $(x+y)^k$ 的二项式展开即可。

题意

给定一棵树，每个点有权值 $a_i$，有 $m$ 个监控摄像头，每个摄像头可以监控子树内距离根小于等于 $k_i$ 的点，如果一个点被某个摄像头监控，则其不能被选择，每个摄像头你可以花费 $c_i$ 的代价黑掉，使其失效，求最大收益。

其中 $3 \le n,m \le 3 \cdot 10^5$。

分析

考虑最大权闭合子图建图，每次选上一个点会获得一个价值，但是能够监控到他的摄像头必须全部黑掉，也就是失去一个价值，因此原题等价于求这个图的最大流。

显然不能直接建图来流，但是这个图很特殊，把图反过来看，源点的流量是流向所有的摄像头，摄像头的流量从对应深度的子树内流出到汇点。

考虑 $dp[u][j]$ 表示 $u$ 点的子树内，深度为 $j$ 的点能提供多少流量，显然对于每个摄像头，尽量从深度大的点流出，这肯定是优的。

上面关于深度的信息可以长链剖分或者启发式合并在 $O(n\log n)$ 的时间内维护。