题解：AT_abc359_g [ABC359G] Sum of Tree Distance

SafariMo · 2024-06-26 15:12:38 · 题解

新做法。

根据颜色分类。

显然 f(i,j)=dep_i+dep_j-2\times dep_{\operatorname{LCA}(i,j)}。

显然统计 i,j 的贡献是简单的。

则统计 \operatorname{LCA}(i,j) 的贡献，则我们让 1\sim i 的所有点都加一，统计所有 1\sim i 的和，注意消除 (i,i) 的贡献，这部分参考 P4211。

显然可以用树链剖分 \mathcal O(n\log^2n) 解决。