企业官网建设流程全解析

写“LCA（下）”之前，先交代一下上篇到了哪里：最常见的倍增法已经讲完，朴素跳父节点也提过一嘴。那为什么还需要再写一篇？因为实战里你会很快发现，倍增并不是万能的——它查询是 O(log n)，但预处理要 O(n log n)；它在线，但不能处理“一次给你一堆查询然后让你批量回答”的最优场景；它对树上路径统计类问题，往往只是垫脚石，不是终点。这篇下篇，我把欧拉序+RMQ、Tarjan离线、树链剖分这三条主流路线全部过一遍，再讲清楚 LCA 在树上差分、路径最值、虚树这些进阶场景里是怎么当“基建”用的。文章照旧按我自己的代码习惯写，C++ 为主，思路部分尽量不依赖语言。

1. 欧拉序 + RMQ：把树压平，LCA 就变成区间最值

倍增法是在树上原地跳，而欧拉序+RMQ 的思路完全相反：我不在树上玩了，我把整棵树按 DFS 访问顺序展开成一个序列，然后用 ST 表预处理这个序列，最后每次查询就是查一段区间里深度最小的点。第一次看到这个思路的人通常会觉得绕，但它其实是“把树上问题变成序列问题”这个通用套路的最佳入门案例。

1.1 欧拉序到底和 DFS 序有什么不同

很多初学者会把欧拉序和 DFS 序搞混。DFS 序是每个节点进入时记录一次，所以序列长度恰好是 n；欧拉序是“每经过一个点就记录一次”，包括从子节点回溯回父节点时也要再记一次父节点。也就是说，欧拉序的长度是 2n-1（每条边会被经过两次），其中每个节点会出现多次，第一次出现的位置记为 first[u]，深度记为 dep[u]。

举一棵最简单的树当例子，根是 1，1 有两个孩子 2 和 3，2 有孩子 4。DFS 从 1 出发，欧拉序大概长这样：

1, 2, 4, 2, 1, 3, 1

每个节点第一次出现的位置分别是：first[1]=0，first[2]=1，first[3]=5，first[4]=2。

这序列有个关键性质：对于任意两个节点 u 和 v，从 first[u] 一路走到 first[v] 这段区间里的深度最小值节点，正好就是 lca(u, v)。比如查 4 和 3，区间是 first[4]=2 到 first[3]=5，序列段是 [4, 2, 1, 3]，深度分别是 2、1、0、1，最小的是 1，而 1 恰好就是 LCA。

这个性质成立的原因很好理解：u 到 v 的路径在 DFS 过程中必然经过它们的最近公共祖先，而这段区间里不可能出现比 LCA 深度更浅的节点，否则那个更浅的节点就应该是它们的公共祖先，矛盾。

1.2 把区间最值转成 RMQ

既然查询变成了“找区间深度最小的节点”，思路就清晰了：用 ST 表预处理欧拉序中每个位置出发、长度为 2^k 的区间里深度最小的节点，查询时把区间 [l, r] 拆成两个可重叠区间取 min。RMQ 问题要求的重叠不影响最值，所以 ST 表这种稀疏表非常合适。

代码实现如下：

const int MAXN = 100005; const int LOGN = 20; vector<int> g[MAXN]; int euler[MAXN * 2], dep[MAXN], first[MAXN]; int st[MAXN * 2][LOGN]; // st[i][j] 表示从 i 开始长 2^j 的区间里深度最小的节点编号 int tot; // 欧拉序长度 void dfs(int u, int fa, int d) { dep[u] = d; first[u] = tot; euler[tot++] = u; for (int v : g[u]) { if (v == fa) continue; dfs(v, u, d + 1); euler[tot++] = u; // 回溯时记录父节点 } } void buildST() { for (int i = 0; i < tot; i++) st[i][0] = euler[i]; for (int j = 1; (1 << j) <= tot; j++) { for (int i = 0; i + (1 << j) - 1 < tot; i++) { int a = st[i][j - 1]; int b = st[i + (1 << (j - 1))][j - 1]; st[i][j] = (dep[a] < dep[b]) ? a : b; } } } int lca(int u, int v) { int l = first[u], r = first[v]; if (l > r) swap(l, r); int k = 31 - __builtin_clz(r - l + 1); int a = st[l][k], b = st[r - (1 << k) + 1][k]; return (dep[a] < dep[b]) ? a : b; }

这里有个容易被忽略的细节：预处理 ST 表之前一定要先 dfs() 把所有节点的 first 和 euler 填好，而且目标树如果不是从 1 开始，要记住进入 dfs 时的根节点参数。__builtin_clz是 GCC 内置函数，用来快速算二进制前导零个数，等价于算 log2。

1.3 在线查询的极致：预处理 O(n log n)，查询 O(1)

这套方案的时间复杂度很好：DFS 一次 O(n)，ST 表预处理 O(n log n)，每次查询 O(1)。相比倍增法的 O(log n) 查询，在查询量极大的场景下优势明显。空间上欧拉序是 2n-1，ST 表要开2n * log(2n)的二维数组，大的时候比较吃内存，尤其 n 到 2e5 时差不多要 2e5 * 18 * 4 字节，约 14MB，还能接受。

我实际写题时，遇到“查询次数达到 n 的两三倍级别”的题目，会优先考虑这个方案，因为 O(1) 查询在常数上确实比倍增友好。不过要注意，ST 表在初始化时需要比较 dep[a] 和 dep[b]，如果两棵子树深度相同，随意选哪个都不影响正确性，因为两者都在区间内，且它们的 LCA 深度更小。这个“取其一”的操作不会引起错误。

2. Tarjan 离线算法：一次 DFS 顺手回答所有问题

欧拉序+RMQ 虽然查询快，但它还是在线算法，需要把所有信息预处理完才能回答。如果题目把查询全部给出来了，而且允许离线处理，那 Tarjan 算法会是代码量最小、常数最小的方案，甚至比 ST 表还好写。

2.1 “离线”到底意味着什么

离线指的是算法可以预先看到所有查询，然后统一安排处理顺序；在线则必须按查询给出的顺序一个一个回答。Tarjan 算法属于离线算法，它把所有查询挂在树上，只跑一次 DFS，在递归的过程中顺带把所有答案填完。

这个算法的核心观察是：DFS 在回溯时，如果某个节点 u 的所有子树都已经访问完，那么 u 和它的兄弟子树中任意已访问节点的 LCA 一定可以追溯到 u 的祖先链上。为了高效维护“当前已经回溯到哪一层”，算法用并查集跟踪每个节点的“当前祖先代表”。

2.2 并查集在算法里的真正角色

Tarjan 算法的框架是：

• 用一个vis[u]数组标记节点是否已访问。
• 用一个anc[u]数组记录节点 u 所属集合的“代表”，这个代表通常是当前 DFS 栈中某层节点。
• DFS 进入节点 u 时，先令anc[u] = u，然后递归访问它的每个孩子。
• 孩子 v 递归结束后，执行merge(u, v)，也就是把 v 所在集合合并到 u 所在集合，并让集合的代表保持为 u。
• 标记vis[u] = true。
• 遍历所有挂在 u 上的查询(u, v)，如果vis[v] == true，那么lca = find(v)。

为什么find(v)就是答案？这需要仔细想：v 已经访问过，说明 v 在 u 的某个兄弟子树里，或者在上层节点回溯过的子树里。此时 v 所在并查集代表，正是当前 DFS 栈中那个“已经回到某个祖先、且尚未离开”的节点，这个祖先就是 u 和 v 的最近公共祖先。如果 v 就在 u 的子树里，vis[v]不一定为 true，因为 u 还没标记为访问，只有 u 的全部子树处理完才会标记，这时如果 v 是 u 祖先，那也不会触发，所以不会误判。

2.3 完整可运行模板

这里给出我用链式前向星存图的方式，查询也用链式前向星存双向边，方便统一处理。

#include <bits/stdc++.h> using namespace std; const int MAXN = 500005; struct Edge { int to, next; } e[MAXN * 2], q[MAXN * 2]; int headE[MAXN], headQ[MAXN]; int cntE = 0, cntQ = 0; int fa[MAXN], ans[MAXN]; bool vis[MAXN]; int n, m; void addEdge(int u, int v) { e[++cntE] = {v, headE[u]}; headE[u] = cntE; } void addQuery(int u, int v) { q[++cntQ] = {v, headQ[u]}; headQ[u] = cntQ; } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void tarjan(int u, int parent) { fa[u] = u; for (int i = headE[u]; i; i = e[i].next) { int v = e[i].to; if (v == parent) continue; tarjan(v, u); fa[v] = u; // 合并子节点到当前节点 } vis[u] = true; for (int i = headQ[u]; i; i = q[i].next) { int v = q[i].to; if (vis[v]) { ans[(i + 1) / 2] = find(v); // 这里需要能对应到查询编号 } } }

上面的代码里，我把查询边也存成双向链式前向星，所以每一条查询实际上占了两个槽位2k-1和2k，用(i+1)/2可以还原出查询编号。如果你用 vector of pairs 存查询，会更直观：

vector<pair<int,int>> queries[MAXN]; // queries[u] = {v, id} ... for (auto &p : queries[u]) { int v = p.first, id = p.second; if (vis[v]) ans[id] = find(v); }

2.4 常被忽略的两个边界

Tarjan 的坑比倍增少，但也不是没有。第一个坑是递归深度。n 到 1e6 时，DFS 递归很容易爆系统栈，这时候要么手动扩栈，要么换用非递归写法。我实测过，大多数 OJ 默认栈够跑到 2e5 左右，再往上就建议#pragma comment(linker, "/STACK:102400000,102400000")或者把 DFS 改成栈模拟。

第二个坑是vis[u]的标记时机。必须等所有孩子递归结束、u 自己也被“完成后”才标记，如果一进函数就标记vis[u] = true，那查询另一端点还在子树里没访问完时，会拿到一个错误的 LCA。这个顺序我见过很多新手写错，排查起来很痛苦，因为答案不是稳定错，而是部分错。

3. 树链剖分：LCA 只是重链操作送你的赠品

树链剖分（Heavy-Light Decomposition, HLD）本身不是为了求 LCA 而设计的，它的目标是“把树上路径操作转化为区间操作”。但因为它天然维护了每个节点到根的跳链结构，顺手求 LCA 也非常高效，而且这一层功夫在后面处理链上查询时早晚要练。

3.1 重链剖分的核心数组

重链剖分要做两遍 DFS。第一遍求出每个节点的子树大小sz[u]、深度dep[u]、父亲father[u]和重儿子son[u]，其中重儿子的定义是子树大小最大的那个孩子。第二遍按照“优先走重儿子”的顺序分配 dfs 序dfn[u]，并记录每个节点所在的链顶top[u]。

这些数组里，LCA 最关心的是top[u]。原理很简单：如果两个节点的top相同，说明它们在同一条重链上，深度浅的那个就是 LCA；如果top不同，就把top深度较深的那个节点整体跳到它top的父节点，然后继续比较。

3.2 跳链版 LCA 代码

int lca(int u, int v) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); u = father[top[u]]; } return dep[u] < dep[v] ? u : v; }

这段代码只有几行，但背后信息量很大。每次循环都把当前链顶更深的节点往上一整条链地跳，跳的次数等于 u 和 v 之间经过的轻边数量加 1。轻边数量是 O(log n) 级别的，因为每跳一次，子树大小至少翻一倍，所以总复杂度 O(log n)。

3.3 第一遍和第二遍 DFS 的完整写法

这里给一个我常用的完整模板：

int sz[MAXN], dep[MAXN], father[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rnk[MAXN]; int dfsClock = 0; void dfs1(int u, int fa) { sz[u] = 1; father[u] = fa; dep[u] = dep[fa] + 1; son[u] = 0; int maxSize = 0; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > maxSize) { maxSize = sz[v]; son[u] = v; } } } void dfs2(int u, int tp) { top[u] = tp; dfn[u] = ++dfsClock; rnk[dfsClock] = u; if (son[u]) dfs2(son[u], tp); // 先走重儿子，保持链上 dfs 序连续 for (int v : g[u]) { if (v == father[u] || v == son[u]) continue; dfs2(v, v); // 轻儿子自成一条链 } }

注意 dfs2 的顺序：必须先递归重儿子，再递归轻儿子。只有这样，同一条重链上的节点才会在 dfs 序上连续分布，这是后面把路径拆成若干个区间操作的基础。如果先走轻儿子，重链上的 dfn 就不连续了，很多带数据结构优化的操作会失效。

3.4 为什么说剖分是“为路径而生”的

单纯求 LCA，树链剖分和倍增差不太多，但剖分真正的价值在于：它可以配合线段树或树状数组，完成路径上的区间更新、区间查询。比如“把 u 到 v 路径上所有点的权值加上 x”“查询 u 到 v 路径上的最大值”，这些操作用倍增只能干瞪眼，用剖分却可以拆成 O(log n) 个区间操作，然后在线段树上跑。

所以我的建议是：如果一道题只让你求 LCA，用倍增或欧拉序+RMQ 足够了；如果题目里还有“路径修改/路径查询”的需求，直接上树链剖分，因为它的 LCA 是顺带算出来的，你再换别的方案反而多写一套框架。

4. 从“找祖先”到“路径问题”：LCA 的高频应用场景

说句实在话，LCA 在真正的竞赛和工程里，几乎从来不作为题目的最终目标。它永远是一个“工具”。你需要掌握的是怎么把这个工具焊进更大的框架里。

4.1 树上两点距离与路径相关计算

最经典的公式是：设dis(u,v)表示树上 u 到 v 的路径长度（边权为 1 时），则有

dis(u, v) = dep[u] + dep[v] - 2 * dep[lca(u, v)]

这个公式虽然简单，但很多树上问题最后都会落到它身上，比如“判断一个点在路径上”也可以用它来判断：点 x 在路径 u-v 上当且仅当

dis(u, x) + dis(x, v) == dis(u, v)

这个等价关系在后面虚树和动态规划题里经常出现，值得记牢。

如果边有权重，把 dep 改成从根到该点的前缀权值和即可，公式形式不变。这是 LCA 最“日常”的用法。

4.2 树上差分：把区间加减搬到树上的关键

树上差分的思路和普通数组差分一模一样：想给路径 u-v 上所有点加 1，可以先在 cnt[u]++，cnt[v]++，然后 cnt[lca]--，cnt[father[lca]]--。DFS 一遍从叶子累加回根，最后 cnt[x] 就表示 x 被多少条路径覆盖。这是经典应用。

如果是给路径 u-v 上所有边加 1，公式变成：

cnt[u]++, cnt[v]++, cnt[lca] -= 2

因为边权通常会“下沉”到子节点，lca 本身不参与边的统计，所以减两次而不是减一次。

我当年学这块时一直搞不清到底该减一次还是减两次，后来自己画了棵树才彻底明白。给一个记忆技巧：点权的时候，lca 也要被覆盖，所以要在 cnt[lca]-- 保留一次覆盖，再在 father[lca]-- 一消除祖先方向的扩散；边权的时候，lca 上方那条边不属于路径，所以直接 cnt[lca] -= 2。

4.3 树上 k 级祖先：倍增表不止能查 LCA

倍增法预处理出来的up[u][j]表，除了能求 LCA，还能直接求任意节点往上跳 k 步的祖先。写法就是按 k 的二进制位拆位：

int kthAncestor(int u, int k) { for (int j = 0; j < LOGN; j++) { if (k & (1 << j)) u = up[u][j]; } return u; }

这个功能在“求路径中间点”“判断路径长度奇偶性”等问题里很常用。还有一个变体是长链剖分求 k 级祖先可以做到 O(1)，但复杂度和代码量都高不少，日常不划算，有需要再说。

4.4 虚树：LCA 当粘合剂

虚树解决的问题是：树上有很多关键点，但 n 很大，关键点很少，如果每次都跑整个树，复杂度无法接受。比如一共有 1e5 个节点，但某次查询只涉及 3 个关键点，你显然不想跑整棵树。虚树的做法是：把关键点按 dfs 序排序，然后依次将相邻两个关键点的 LCA 加入候选集合，最后再按 dfs 序建一棵“只包含关键点和它们 LCA”的小树。

这里面 LCA 是绝对的灵魂。没有 LCA，关键点之间的祖先关系完全无法压缩。构建虚树的单调栈算法，核心步骤是：

• 将关键点按 dfn 排序。
• 维护一个栈，栈中元素从底到顶是当前节点到根的路径上需要保留的节点。
• 每加入一个新点 u，取栈顶元素 p = stk.back()，计算 l = lca(u, p)。
• 如果 l == p，说明 u 在 p 的子树内，直接把 u 入栈。
• 如果 l != p，说明 u 不在 p 的子树内，此时不断弹栈，直到栈顶深度小于等于 l 的深度，然后补上 l 作为新节点，并把弹出去的节点的父指针指向 l。

这个过程非常容易写错，我建议手跑几组例子再上考场。不过它的核心依赖就是 LCA 查询函数，所以只要 LCA 写得稳，虚树就成功了一半。

4.5 路径最大/最小边权查询

另一种常见套路是：把倍增表中的up[u][j]扩展为mx[u][j]，表示从 u 向上跳 2^j 步的路径上边权的最大值。查询 u-v 路径最大边权时，先求 lca，然后分别从 u 和 v 向上倍增到 lca 以下，沿途合并 mx 值。这个技巧在最小生成树相关题目（例如次小生成树）里几乎是必考的，LCA 又一次作为核心工具出现。

5. 四套方案怎么选：一份带数值的决策指南

我知道看到这里，很多人会问：学了四种方法，考试到底用哪个？这里我给一个自己实践的选型表，顺便把最容易坑人的几个点也一并列出来。

5.1 复杂度对比总览

这里的“在线”指的是能否按输入顺序立即回答查询。多数题没有强制在线，但如果你写的是交互题，就只能用在线方案。

• 查询次数大于 1e6 且 n 在 2e5 以内：优先欧拉序+RMQ，查询常数最小。
• 查询次数一般（和 n 同数量级）：倍增法最省心，代码量最小。
• 所有查询提前给定，n 和 m 都很大：Tarjan 离线，常数小而且省内存。
• 题目还要做路径加、路径和、子树覆盖等操作：无脑树链剖分，它求 LCA 只是副产品。

5.2 翻车点与注意事项

我在不同平台用这几种算法写过不少题，踩过的坑可以列一长串，这里挑几个最典型的。

倍增表的边界：up[u][j]在 j 超过 log 深度时需要是 0，否则求 LCA 循环会访问到随机地址。建表时要把数组清成 0，并且保证根节点的 father 是 0。

欧拉序的长度：很多写着写着数组只开了 n，实际要 2n-1，一跑边界就崩。建议直接开2 * MAXN，别省那一个位置。

Tarjan 的根节点标记：递归进入根节点时，记得也要执行vis[root] = true，否则挂在根节点上的查询会漏答。

树链剖分 dfs2 的重儿子优先级：必须把重儿子放在最前面递归，否则 dfn 不连续，后续所有区间操作都会出错。这个顺序问题不像逻辑错误，而是一种“玄学 bug”，数据一多就 WA，还特别难定位。

递归爆栈：树如果是链状，递归 DFS 深度会达到 n。n 到 5e5 时，系统栈很容易溢出。比较省事的办法是写一个手写栈模拟，或者用欧拉序+RMQ 的方案替代递归 DFS。我自己在 n 很大时更倾向用 C++ 的std::function递归前先设置好ios::sync_with_stdio(false)，同时尽量缩递归深度。

5.3 一个个人习惯

我自己的习惯是：比赛时优先写倍增，因为它代码短、调试快；但如果题目明确说查询次数会很大，我绝不犹豫，直接写欧拉序+RMQ。平时练习刷题时，树链剖分的 LCA 我至少每隔一段时间就默写一遍，因为这个代码虽然逻辑不复杂，一旦不熟就会在细节上卡很久。Tarjan 离线我反而用得少，但它让我理解了“离线处理”的威力，这个思想在很多高级数据结构题里都会反复出现。

最后再分享一个小技巧：如果一道题的数据范围不允许递归 DFS，又必须用树链剖分，可以先把 DFS 改成显式栈的后序遍历，但这样代码会变长很多。我的妥协方案是：能用递归就用递归，遇到明显链状的毒瘤数据，就先测一下递归深度，深度超过阈值就换欧拉序+RMQ，不跟栈空间硬刚。做算法题，思路清晰永远比秀操作重要。