4211

[LNOI2014] LCA 题目描述 给出一个 \(n\) 个节点的有根树（编号为 \(0\) 到 \(n-1\)，根节点为 \(0\) ）。 一个点的深度定义为这个节点到根的距离 \(+1\)。 设 \(dep[i]\) 表示点 \(i\) 的深度，\(\operatorname{LCA}(i, ......

$\color{purple}\text{P4211 [LNOI2014]LCA}$ 解题方法 可以发现一个结论：两个点到根节点的重合路径的长度即为他们 $LCA$ 的深度。所以我们把 $[l,r]$ 之间的点到根节点路径上各加一，再查询 $z$ 到根节点的路径的值之和即为 $\sum_{i=l}^ ......