AC6 Round C sol

· · 题解

假定树以 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 一次点分慢一些但是好写很多，详情请咨询 墨染空 神仙（雾）。