P6626 消息传递

· · 题解

虽然是一眼的点分治模版题，还不带修。

但这是 O(n \log n) 的，有一个 O(n) 的长链剖分解法。

暴力 DP 很显然吧，设 f_{u,j} 为以 u 为子树，距离 u 为 j 的方案数。

转移：

f_{u,j}=\sum_{(u,v) \in E} f_{v,j-1}

这显然长链剖分优化 DP 啊，优化过后就是 O(n) 的了。

然后，询问就往上倍增然后容斥一下就行了。

目前是 Luogu 与 Loj 最优解。

code