自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:33:03，当前版本为作者最后更新于2021-04-21 22:56:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

假定树以 $1$ 为根，考虑将 $u$ 的答案分为两类：

I 两端点 LCA 是 $u$ 的路径

长链剖分优化 DP，每一次暴力合并短链的时候到长链里面统计一下答案。

用树状数组维护长链，复杂度为 $O(n\log n)$。

II 两端点 LCA 不是 $u$ 的路径

将答案记为 $b_u$，考虑 $b_u$ 与 $\sum_{(u,v)\in E}b_v$ 相差多少。

相差的有两部分：

1. 过一个孩子，并且 LCA 是 $u$ 的路径。如果一端是 $u$，则需要减 1 次；否则需要减 2 次。
2. 从 $u$ 开始向上走的路径，需要加上。

将 2 看作是所有从 $u$ 开始的路径减去从 $u$ 开始向下的路径。

将 1 和 2 加起来，$b_u$ 就是 所有从 $u$ 开始的路径数量 减去 所有 LCA 是 $u$ 的路径数量的 2 倍 加上 $\sum_{(u,v)\in E}b_v$。

所有从 $u$ 开始的路径数量使用点分治求出，在合并子树的时候按照子树树高排序之后暴力合并前缀和，即可做到总复杂度 $O(n\log n)$。

好像有个两次点分然后不用做 dp 的方法，比 std 一次点分慢一些但是好写很多，详情请咨询 墨染空 神仙（雾）。