最近公共祖先 LCA

---

最近公共祖先是指在一棵有根树中，两个节点向根节点路径上的第一个交汇点。求解LCA问题，本质上是高效地找到树中任意两个节点的这个最深公共祖先。

暴力求解法需要沿着父指针回溯并比较路径，但效率低下。为此，我们采用倍增等算法进行优化。该算法通过预处理，让每个节点存储其向上第1、2、4...级的祖先信息。在查询时，我们先将两个节点调整到同一深度，然后利用二进制拼凑的思想，让它们一同跳跃式地向上寻找，直到找到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]$$

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

---

【思维导图】

【题目知识点分类】