最近公共祖先

最近公共祖先 LCA

1. 倍增求 LCA

核心

• 在一棵以 $1$ 为根的树上，最近公共祖先 $LCA(u,v)$ 是同时为 $u,v$ 祖先、且深度最大的结点。
• 倍增思想：预处理每个点向上跳 $2^k$ 步到达的祖先 fa[u][k]，并记录 dep[u]（深度）。
• 预处理复杂度：$O(n\log n)$
单次查询复杂度：$O(\log n)$（适用于动态多次询问）

---



1.1 倍增预处理：DFS/BFS + 父节点倍增表



• fa[u][0]：$u$ 的父节点
• fa[u][k] = fa[ fa[u][k-1] ][k-1]：表示从 $u$ 往上跳 $2^k$ 步可以到达的节点
• dep[u]：深度（根深度常设为 $1$ 或 $0$）

---



1.2 查询流程



给定 $u,v$：



Step 1：把更深的点抬到同一深度



令 $u$ 更深（若不是则交换），设 $d=dep[u]-dep[v]$，按二进制拆分：

• 若 $d$ 的第 $k$ 位为 $1$，令 $u = fa[u][k]$



Step 2：同时向上跳，找到分叉点



若此时 $u=v$，答案就是该点。否则从大到小枚举 $k$：

• 若 fa[u][k] != fa[v][k]，则同时跳：
- $u = fa[u][k],\ v = fa[v][k]$



Step 3：返回父亲



最后 $u,v$ 的父亲就是 LCA：

• $$LCA(u,v)=fa[u][0]$$

---



常见扩展



• 求两点距离
设 $w=LCA(u,v)$：
$$ dist(u,v)=dep[u]+dep[v]-2\cdot dep[w] $$

• 路径相关统计：配合“树上差分”非常常用（见第 2 部分）。

---



2. 树上差分



树上差分常用于树上的路径修改，如对路径上的所有点或者所有边同时进行修改，，最后一通过次 DFS 汇总，得到每个点/每条边被经过的次数或累计权值。和一维差分类似，适用于修改多而查询少的情况。

---



2.1 树上点差分（统计“点被路径覆盖次数”）





目标



对于很多次操作：给路径 $(u,v)$ 上每个点加 $1$（或加权值 $x$），最终求每个点的累计值。



差分标记（一次路径 u-v）



设 $w=LCA(u,v)$，当我们希望将路径上所有点都加上权值 $x$ 的情况下， 可以做如下操作，则对数组 tag[] 做：



tag[u] += x; 
tag[v] += x;
tag[w] -= x;
tag[fa[w][0]] -= x;


如下图中 $7$ 号点到 $8$ 号点之间路径上所有边都加上权值 $x$，可以做出图中操作。



而后使用DFS从下往上进行贡献累加，可以实现只修改路径上的点。



汇总方式



最后从叶子向根做一次 DFS（后序），把子树贡献往上加：

• $$tag[u] \mathrel{+}= \sum_{son} tag[son]$$

汇总完成后，tag[x] 就是点 $x$ 被多少条路径覆盖（或累计权值）。

---



2.2 树上边差分（统计“边被路径覆盖次数”）





目标



对于很多次操作：给路径 $(u,v)$ 上每条边加 $1$（或加权值 $x$ ），最终求每条边的累计值。

在边差分中，我们的 tag 数组记录的是每个点到其父节点的边的数值。



差分标记（一次路径 u-v）



设 $w=LCA(u,v)$， 当我们希望将路径上所有边都加上权值 $x$ 的情况下， 可以做如下操作，





tag[u] += x; 
tag[v] += x; 
tag[w] -= 2 * x;



如下图中 $7$ 号点到 $8$ 号点之间路径上所有边都加上权值 $x$，可以做出图中操作。





而后使用DFS从下往上进行贡献累加，可以实现只修改路径上的边。





汇总方式



最后从叶子向根做一次 DFS（后序），把子树贡献往上加：

• $$tag[u] \mathrel{+}= \sum_{son} tag[son]$$