LCA简介

处理树上点与点关系的问题时（例如，最简单的，树上两点的距离），常常需要获知树上两点的最近公共祖先（Lowest Common Ancestor，LCA）。如下图所示：

截屏2024-02-20 11.07.05

其中，2号点是7号点和9号点的最近公共祖先。这个概念还是很容易懂的。

注意，一定要是有根树，不一定是二叉树。

代码实现方法

  1. 向上标记法 $O(n)$​

    先从两点中任选一点，向根节点遍历，把所有途径的节点（包括自己）标记一遍（表示是该节点的祖先）

    再让另一个点向根节点遍历，当第一次遇到被标记过的点时，该点为两点的最近公共祖先。

  2. 倍增法（用得最多）代码实现：祖孙询问——倍增法实现LCA $O(n\log n)$​

    • 预处理

      下面两个需要被预处理出来的数组可以在一次宽度优先搜索中预处理出来。

      • 预处理数组fa,fa[i, j]表示从$i$开始，向上走$2^j$步所能到的节点。$0 \le j \le \log n$。

        若从i开始向上跳$2^j$步会跳过根节点，那么fa[i, j]=0

        用上图举例：fa[7,0]=4, fa[7,1]=2, fa[7,2]=0

        • j=0

          fa[i, j]为i的父节点

        • j>0

          fa[i, j] = fa[fa[i,j-1], j-1]可以通过递推的方式来求。

      • 预处理深度数组depth, depth[i]表示i的深度（到根节点的距离加一）,特殊的depth[0]=0

        用上图举例：depth[1]=1, depth[2]=2, depth[4]=3, depth[7]=4, depth[9]=5

    • 求最近公共祖先

      这里求节点7（x）和节点6（y）的最近公共祖先距离。

      1. 先将两个点跳到同一层（同一深度） $O(\log n)$

        从大往小枚举k：

        • depth[fa[x, k]] >= depth[y]，跳

          x = fa[x, k]

          由于设置了跳过根节点则fa[x, k]=0, depth[0]=0<depth[y]，所以一定可以跳到同一层。

          根据例子：

          此时x=fa[x,0]=4。

     2.   让两个点同时往上跳，一直跳到它们最近公共祖先的**下一层** $O(\log n)$​

          从大到小枚举k:

          -   `fa[x,k]] != fa[y,k]`，跳，跳之后两个节点都是最近公共祖先的子节点

              `x=fa[x, k], y=fa[y,k]`

              由于设置了跳过根节点则`fa[x,k]=fa[y,k]=0`,，所以当两者都跳过根节点时，不会跳。



          根据例子：

          x=4,y=6

          `fa[x,0]=2,fa[x,1]=1,fa[x,2]=0`

          `fa[y,0]=3,fa[y,1]=1,fa[y,2]=0`

          可能实际k=15开始枚举，这里从3开始举例：

          -   `k=3`

              `fa[x,3]] = 0, fa[y,3] = 0`，不跳（k>3时也一样，不会跳）

          -   `k=2`

              `fa[x,2] = 0, fa[y,2] = 0`，不跳

          -   `k=1`

              `fa[x,1] = 1, fa[y,1] = 1`，不跳

          -   `k=0`

              `fa[x,0] = 2, fa[y,0] = 3`，跳

              于是`x=fa[x,0]=2,y=fa[y,0]=3`

              最终公共祖先为fa[x,0]=fa[2,0]=1。

  1. Tarjan——离线求LCA $O(n+m)$ n是节点数量，m是查询数量

    「离线」：直接求出两两节点的最近公共祖先，再询问时直接返回。

    本质是对向上标记法的优化。

    在深度优先遍历时，将所有点分成三大类。

    1. 已经遍历过，且回溯过的点
    2. 正在搜索点分支
    3. 还未搜索到的点

    如图：

    截屏2024-02-20 20.43.00

    当前遍历的节点为x，其中绿色圈包含的部分为已经遍历过的节点，正在搜索的分支就为红色圈包含的部分，黑色圈包含的部分就还没有搜索到。

    有了三种分类，在每次搜索时，将当前节点通过并查集进行合并，例如上图的y节点已经通过并查集和节点a划分到同一类中，节点z已经通过并查集和节点b划分到同一类中。

    在搜索节点x时，需要与已经遍历过的节点即绿色圈中的节点计算最近公共祖先，计算其最近公共祖先可以判断其在的并查集，所以可以很快得到最近公共祖先。且代表元素就是其并查集上的根节点。例如上图，x和y的最近公共祖先为a，x和z的最近公共祖先为b。

    这里可能就会有疑问了，为什么z和b现在是在一个并查集中，z、b和a不也是一个并查集吗。其实是因为现在还没搜索b，仅仅是这条分支，当搜索b结束后，就会把b所在的并查集和a所在的并查集做合并，合并后的祖宗节点为a。所以重点是合并并查集的时机，其时机为回溯之后。简单来说就是中序遍历多叉树。

算法总结

常用算法实现：

  • 向上标记法: $O(n)$

  • 倍增法: 预处理复杂度是$O(n \log n)$ , 每次询问时间复杂度为$O(\log n)$,是一种在线算法

  • 采用Tarjan算法求解，复杂度$O(α(n)+Q)$，属于离线算法

  • 利用树链剖分求解，复杂度预处理$O(n)$，单次查询$O(\log n)$，属于在线算法。

    但是树链剖分求解LCA中的行为（强调是行为，不是思想）与倍增法类似，加之代码量大，不易调试，所以仅在讲倍增法的时候有所涉及，不详细展开。

  • 利用欧拉序转化为RMQ问题，用ST表求解RMQ问题，预处理复杂度$O(n + n \log n)$，每次询问的复杂度为$O(1)$​，也是在线算法。

这里建议在线算法和离线算法都分别背一个板子就可以，贪多嚼不烂，在考场上选择也是一个麻烦。我背的是倍增法和tarjan。模版见下。

祖孙询问——倍增法实现LCA

题目描述

给定一棵包含$n$个节点的有根无向树，节点编号互不相同，但不一定是1～n。

有m个询问，每个询问给出了一对节点的编号x和y，询问x和y的祖孙关系。

输入格式

输入第一行包括一个整数表示节点个数。

接下来n行每行一对整数a和b，表示a和b之间有一条无向边。如果b是-1，那么a就是树的根；

第n+2行是一个整数m表示询问个数；

接下来m行，每行两个不同的正整数x和y，表示一个询问。

输出格式

对于每个询问，若x是y的祖先则输出1，若y是x的祖先则输出2，否则输出0.

数据范围

$1 \le n, m \le 4*10^4$,

$1 \le 每个节点编号 \le 4*10^4$

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出样例

1
2
3
4
5
1
0
0
0
2

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int N = 40010, M = N*2;

int n, m;
int h[N], e[M], ne[M], idx; // 链式前向星存图
int depth[N], fa[N][16]; // 最多2^16层
int q[N]; // 队列

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 预处理fa数组和depth数组
void bfs(int root) {
	memset(depth, INF, sizeof(depth));
	depth[0] = 0, depth[root] = 1;
	int hh = 0, tt = 0;
	q[0] = root;

	// 使用宽度优先搜索（怕深度优先搜索爆栈）
	while (hh <= tt) {
		int t = q[hh++];
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if (depth[j] > depth[t] + 1) {
				depth[j] = depth[t] + 1;
				q[++tt] = j;
                
				fa[j][0] = t;
				for (int k = 1; k <= 15; ++k)
					fa[j][k] = fa[fa[j][k-1]][k-1];
			}
		}
	}
}

int lca(int a, int b) {
	// 跳到同一层
	if (depth[a] < depth[b]) swap(a, b); // 令 a 在 b 的下面（更深），让 a 往上走
	for (int k = 15; k >= 0; --k) {
		if (depth[fa[a][k]] >= depth[b]) // 跳
			a = fa[a][k];
	}
	if (a == b) return a;

	// 同时往上跳
	for (int k = 15; k >= 0; --k)
		if (fa[a][k] != fa[b][k]) {
			a= fa[a][k];
			b= fa[b][k];
		}
	return fa[a][0];
}

int main() {
	cin >> n;
	int root = 0;
	memset(h, -1, sizeof(h));

	int a, b;
	for (int i = 0; i < n; ++i) {
		cin >> a >> b;
		if (b == -1) root = a;
		else { // 无向边
			add(a, b);
			add(b, a);
		}
	}

	// 预处理fa数组和depth数组
	bfs(root);

	cin >> m;
	while (m--) {
		cin >> a >> b;
		int p = lca(a, b);
		if (p == a) puts("1");
		else if (p == b) puts("2");
		else puts("0");
	}
    
    return 0;
}

距离——Tarjan实现LCA

题目描述

给定一棵包含$n$个节点的有根无向树，多次询问两点之间的最短距离。

所有节点的编号是$1, 2,3,\cdots,n$​。

提示：树上求距离的一个小技巧

把每个点与根节点的距离预处理出来，假设存到数组d中，先有节点x和节点y，两者的最近公共祖先为z。则节点x和节点y的距离为：d[x]+d[y]-2*d[z]。（可以自行画图理解）。

输入格式

输入第一行包含两个整数$n$和$m$。$n$表示节点数，$m$表示询问次数；

接下来$n-1$行,每行三个整数$x,y,z$，表示$x$和$y$之间有一条无向边，边长为$k$。

接下来m行，每行两个不同的正整数$x$和$y$​，表示一个询问。

输出格式

共$m$行，对于每次询问，输出一行询问结果。

数据范围

$2 \le n \le 10^4$,

$1 \le m \le 2*10^4$,

$0 \lt k \le 100$,

$1 \le x,y \le n$

输入样例1

1
2
3
4
2 2
1 2 100
1 2
2 1

输出样例1

1
2
100
100

输入样例2

1
2
3
4
5
3 2
1 2 10
3 1 15
1 2
3 2

输出样例2

1
2
10
25

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

const int N = 20010, M = N*2;

int n, m;
int h[N], e[M], w[M], ne[M], idx; // 树
int p[N]; // 并查集和祖宗节点数组
int dist[N]; // 每个节点与根节点的距离
int st[N]; // 每个节点的类型, 0表示未遍历的节点，1表示正在遍历的节点，2表示遍历结束回溯后的节点
int res[N];
vector<pii> query[N]; // first存查询的另一个点，second位查询编号

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa) {
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == fa) continue;
		dist[j] = dist[u] + w[i];
		dfs(j, u);
	}
}

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

void tarjan(int u) {
	st[u] = 1;

	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (!st[j]) { // 类型为0，没被遍历过，则遍历
			tarjan(j);
			// 回溯，把j合并到u所在的并查集（u为j的父节点）
			p[j] = u;
		}
	}

	for (auto item: query[u]) { // 遍历所有和u节点有关的查询
		int y = item.first, id = item.second;
		if (st[y] == 2) { // 已经回溯过
			int anc = find(y); // 最近公共祖先为y在并查集中的祖宗节点
			res[id] = dist[u] + dist[y] - 2*dist[anc];
		}
	}

	st[u] = 2;
}

int main() {
	cin >> n >> m;

	// 建图（树）
	memset(h, -1, sizeof(h));
	int a, b, c;
	for (int i = 0; i < n - 1; ++i) {
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}

	// 读入查询
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		if (a != b) {
			query[a].push_back({b, i});
			query[b].push_back({a, i});
		}
	}

	// 初始化并查集
	for (int i = 1; i <= n; ++i) p[i] = i;

	// 预处理dist数组这里是无向边，随便选择节点1作为根节点
	dfs(1, -1);
	tarjan(1); 

	for (int i = 0; i < m; ++i) cout << res[i] << endl;
    
    return 0;
}