02.12.3 LCA 与树上算法
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.12 图与字符串进阶
覆盖范围
- LCA 倍增法与 Tarjan 离线
- 树链剖分
- 树上差分
- 树的重心与直径
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.12.3-001 | LCA 暴力法 | 基础 | ★★★ |
| 02.12.3-002 | LCA 倍增法 | 进阶 | ★★★★ |
| 02.12.3-003 | LCA Tarjan 离线 | 高级 | ★★★ |
| 02.12.3-004 | 树链剖分重链 | 高级 | ★★★ |
| 02.12.3-005 | 树上差分 | 进阶 | ★★★ |
| 02.12.3-006 | 树的重心与直径 | 基础 | ★★★★ |
| 02.12.3-007 | 倍增预处理 | 进阶 | ★★★★ |
| 02.12.3-008 | 树链剖分应用 | 高级 | ★★★ |
02.12.3-001 LCA 暴力法
频率 ★★★ | 难度 基础
一句话结论
LCA(最近公共祖先)暴力法:先把两个节点提到同一深度,再一起往上走,直到相遇;每次 O(depth),预处理 O(n),查询 O(depth)。
概念解释
- LCA:两个节点最近的公共祖先。
- 深度:节点到根的距离。
- 暴力:先提深度,再一起上走。
原理流程
- DFS 预处理每个节点深度和父节点。
- 查询 LCA(u, v):
- 若 depth[u] > depth[v],u 往上走。
- 直到 depth[u] == depth[v]。
- 若 u == v,返回 u。
- 否则 u 和 v 一起往上走,直到相遇。
代码 / 示例
class LCABrute {
private final int[] parent, depth;
LCABrute(int n, int[] parent, int[] depth) {
this.parent = parent; this.depth = depth;
}
int lca(int u, int v) {
while (depth[u] > depth[v]) u = parent[u];
while (depth[v] > depth[u]) v = parent[v];
while (u != v) { u = parent[u]; v = parent[v]; }
return u;
}
}
常见误区
- 误区:不提深度直接一起上走;正解:先提深度,再一起上走。
- 误区:u == v 时不返回;正解:u == v 时已经是 LCA。
追问 / 延伸
- Q:时间复杂度? A:预处理 O(n),查询 O(depth)。
- Q:暴力法缺点? A:树高时慢(如链状树 O(n))。
02.12.3-002 LCA 倍增法
频率 ★★★★ | 难度 进阶
一句话结论
倍增法预处理 up[k][u] 表示 u 的 2^k 级祖先;查询时先提深度(用二进制分解),再一起上走(用二进制分解);预处理 O(n log n),查询 O(log n)。
概念解释
- up[k][u]:u 的 2^k 级祖先。
- 预处理:up[0][u] = parent[u],up[k][u] = up[k-1][up[k-1][u]]。
- 查询:二进制分解深度差和深度差。
原理流程
- 预处理:up[0][u] = parent[u],up[k][u] = up[k-1][up[k-1][u]]。
- 查询 LCA(u, v):
- 提深度:把 u 提到和 v 同深度,用二进制分解深度差。
- 若 u == v 返回。
- 一起上走:从大到小枚举 k,若 up[k][u] != up[k][v],u = up[k][u],v = up[k][v]。
- 返回 parent[u]。
代码 / 示例
class LCABinary {
private final int[][] up;
private final int[] depth;
private final int log;
LCABinary(int n, int root, int[] parent, int[] depth) {
this.log = (int)(Math.log(n) / Math.log(2)) + 1;
this.depth = depth;
up = new int[log][n];
for (int i = 0; i < n; i++) up[0][i] = parent[i];
up[0][root] = root;
for (int k = 1; k < log; k++)
for (int i = 0; i < n; i++)
up[k][i] = up[k - 1][up[k - 1][i]];
}
int lca(int u, int v) {
if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
int diff = depth[u] - depth[v];
for (int k = 0; k < log; k++)
if ((diff & (1 << k)) != 0) u = up[k][u];
if (u == v) return u;
for (int k = log - 1; k >= 0; k--)
if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
}
常见误区
- 误区:提深度时从小到大枚举 k;正解:提深度可以任意顺序,但一起上走必须从大到小。
- 误区:root 的 parent 设为 -1;正解:root 的 parent 设为 root,避免越界。
追问 / 延伸
- Q:时间复杂度? A:预处理 O(n log n),查询 O(log n)。
- Q:倍增法优点? A:查询 O(log n),适合多次查询。
02.12.3-003 LCA Tarjan 离线
频率 ★★★ | 难度 高级
一句话结论
Tarjan 离线 LCA:DFS 遍历,子树访问完后合并到父节点(并查集);查询时若两个节点都已访问,则 LCA 是 find(v);O(n + Q)。
概念解释
- 离线:先读所有查询,再处理。
- 并查集:子树访问完合并。
- 查询:两个节点都访问过,LCA = find(v)。
原理流程
- DFS u:标记 u 为已访问。
- 递归子节点 v,访问完 v 后 union(u, v)。
- 处理 u 的查询:若 v 已访问,答案 = find(v)。
- 回溯。
代码 / 图示
Tarjan 离线 LCA:
DFS u
标记 u visited
for child v:
dfs(v)
union(u, v)
for query (u, v):
if v visited:
ans = find(v)
常见误区
- 误区:Tarjan 在线;正解:Tarjan 离线,需要先读所有查询。
- 误区:合并时方向错;正解:子树访问完后合并到父节点。
追问 / 延伸
- Q:时间复杂度? A:O(n + Q),Q 为查询数。
- Q:Tarjan vs 倍增? A:Tarjan 离线 O(n+Q),倍增在线 O(log n)。
02.12.3-004 树链剖分重链
频率 ★★★ | 难度 高级
一句话结论
树链剖分把树拆成若干条重链;每个节点记录重儿子(子树最大的儿子)、轻儿子;重链用 DFS 连续编号;树上路径查询转化为区间查询(线段树)。
概念解释
- 重儿子:子树最大的儿子。
- 重链:重儿子连起来的链。
- 轻儿子:非重儿子。
- 编号:重链 DFS 连续编号,方便线段树。
原理流程
- 第一次 DFS:求 size、parent、depth、重儿子。
- 第二次 DFS:重链优先编号,记录 top(链顶)。
- 路径查询:u 和 v 不在同一条重链时,跳 top,查询区间;直到同一条重链。
代码 / 图示
树链剖分:
重儿子:子树最大
重链:重儿子连起来
top:链顶
路径查询:跳 top,线段树区间查询
常见误区
- 误区:两次 DFS 顺序;正解:第一次求 size 和重儿子,第二次编号。
- 误区:跳 top 时方向错;正解:top 深度大的先跳。
追问 / 延伸
- Q:时间复杂度? A:预处理 O(n),路径查询 O(log^2 n)。
- Q:树链剖分用于什么? A:树上路径查询、子树查询。
02.12.3-005 树上差分
频率 ★★★ | 难度 进阶
一句话结论
树上差分:点差分或边差分;路径 u-v 加 val:diff[u] += val、diff[v] += val、diff[lca] -= val、diff[parent[lca]] -= val;最后 DFS 求和。
概念解释
- 点差分:路径上的点加 val。
- 边差分:路径上的边加 val。
- 差分公式:u、v 加 val,lca 减 val,parent[lca] 减 val。
原理流程
- 路径 u-v 加 val:diff[u] += val、diff[v] += val、diff[lca(u,v)] -= val、diff[parent[lca(u,v)]] -= val。
- DFS 求和:sum[u] = diff[u] + sum[子节点]。
代码 / 示例
// 点差分:路径 u-v 加 val
diff[u] += val;
diff[v] += val;
diff[lca] -= val;
if (parent[lca] != -1) diff[parent[lca]] -= val;
// DFS 求和
int dfs(int u) {
int sum = diff[u];
for (int v : children[u]) sum += dfs(v);
ans[u] = sum;
return sum;
}
常见误区
- 误区:lca 不减 val;正解:lca 要减 val,否则重复计算。
- 误区:parent[lca] 不减;正解:parent[lca] 要减,否则 lca 的祖先也被加了。
追问 / 延伸
- Q:边差分? A:边差分在子节点上,公式略不同。
- Q:时间复杂度? A:预处理 O(n),查询 O(1),最后求和 O(n)。
02.12.3-006 树的重心与直径
频率 ★★★★ | 难度 基础
一句话结论
重心:删除后最大子树最小的节点;直径:最远两点的距离;都用 DFS 求;重心性质:重心的所有子树大小 <= n/2。
概念解释
- 重心:删除后最大子树最小。
- 直径:最远两点距离。
- 性质:重心所有子树 <= n/2。
原理流程
- DFS 求 size[u]。
- 重心:枚举每个节点,maxPart = max(n - size[u], max(size[child])),取最小。
- 直径:DFS 求每个节点的最长两条链,和即为直径候选。
代码 / 示例
// 求重心
int dfsSize(int u) {
int size = 1;
int maxPart = 0;
for (int v : children[u]) {
int s = dfsSize(v);
size += s;
maxPart = Math.max(maxPart, s);
}
maxPart = Math.max(maxPart, n - size);
if (maxPart < minMax) { minMax = maxPart; center = u; }
return size;
}
// 求直径
int dfsDiameter(int u) {
int max1 = 0, max2 = 0;
for (int v : children[u]) {
int d = dfsDiameter(v) + 1;
if (d > max1) { max2 = max1; max1 = d; }
else if (d > max2) max2 = d;
}
diameter = Math.max(diameter, max1 + max2);
return max1;
}
常见误区
- 误区:重心只看子树;正解:还要看父方向(n - size[u])。
- 误区:直径是最长链;正解:直径是最远两点距离,可能经过当前节点。
追问 / 延伸
- Q:重心性质? A:重心所有子树 <= n/2。
- Q:直径性质? A:树的直径是唯一路径(可能多条)。
02.12.3-007 倍增预处理
频率 ★★★★ | 难度 进阶
一句话结论
倍增预处理 up[k][u]:up[0][u] = parent[u],up[k][u] = up[k-1][up[k-1][u]];用于 LCA、求 k 级祖先、求路径长度;预处理 O(n log n)。
概念解释
- up[k][u]:u 的 2^k 级祖先。
- 递推:up[k][u] = up[k-1][up[k-1][u]]。
- 应用:LCA、k 级祖先、路径长度。
原理流程
- up[0][u] = parent[u]。
- up[k][u] = up[k-1][up[k-1][u]]。
- 查 k 级祖先:二进制分解 k。
代码 / 示例
// 预处理
for (int k = 1; k < log; k++)
for (int i = 0; i < n; i++)
up[k][i] = up[k - 1][up[k - 1][i]];
// 查 k 级祖先
int kthAncestor(int u, int k) {
for (int i = 0; i < log; i++)
if ((k & (1 << i)) != 0) u = up[i][u];
return u;
}
常见误区
- 误区:root 的 parent 设为 -1;正解:设为 root 或 0,避免越界。
- 误区:k 超过树高;正解:需要处理 k 超过树高的情况。
追问 / 延伸
- Q:倍增法用于什么? A:LCA、k 级祖先、路径长度。
- Q:时间复杂度? A:预处理 O(n log n),查询 O(log n)。
02.12.3-008 树链剖分应用
频率 ★★★ | 难度 高级
一句话结论
树链剖分用于:树上路径查询(和、最大值)、子树查询、路径修改、子树修改;转化为线段树区间操作;O(log^2 n) 每次操作。
概念解释
- 路径查询:u 到 v 的路径和/最大值。
- 子树查询:u 的子树和/最大值。
- 路径修改:u 到 v 的路径加 val。
原理流程
- 路径查询:u 和 v 不在同一条重链时,跳 top,线段树查询区间;直到同一条重链,再查询区间。
- 子树查询:子树编号连续,直接线段树区间查询。
代码 / 图示
路径查询 u-v:
while top[u] != top[v]:
if depth[top[u]] < depth[top[v]] swap
query(pos[top[u]], pos[u])
u = parent[top[u]]
if depth[u] > depth[v] swap
query(pos[u], pos[v])
常见误区
- 误区:跳 top 时方向错;正解:top 深度大的先跳。
- 误区:区间方向错;正解:pos[top[u]] 到 pos[u],top 深度小所以 pos 小。
追问 / 延伸
- Q:时间复杂度? A:O(log^2 n),每次跳 top O(log n),线段树 O(log n)。
- Q:树链剖分 vs 倍增? A:倍增只能查询路径信息,树链剖分支持修改和复杂查询。
待整理清单
- [ ] 动态树 Link-Cut Tree
- [ ] 虚树
- [ ] 树上差分综合题