P4211 [LNOI2014] LCA 题解

给定一棵树，对于每个给定的 $l, r, z$，求：

\sum_{i = l}^r dep[\operatorname{LCA}(i, z)]

考虑转化。dep[\operatorname{LCA}(x, y)] 表示从根节点到 \operatorname{LCA}(x, y) 节点经过的节点数，其相当于对于根节点到 x 的路径上每个点都 $+ 1$，求从根节点到 y 的路径上所有节点的权值和。

因此，考虑使用树链剖分，对于每次操作，对 root \rightarrow i, i \in [l, r] 的路径上每个点权值 $+ 1$，并求 root \rightarrow z 的路径上所有节点的权值和。

然后，很自然地，可以分别计算 l - 1, r 时的答案，并维护差分求解。

但是，若是每次操作都清除线段树，显然有点浪费。考虑将询问离线为 2 \times m 次 [1, l - 1 \text{or } r] 时的查询，按照右端点排序求解。

总时间复杂度 \operatorname O(n \log^2 n)