最近公共祖先

发表于 分类于 本文字数： 781 阅读时长 ≈ 3 分钟
介绍最近公共祖先（LCA）问题的三种主流解法：倍增、树链剖分与 Tarjan。

元旦快乐！

最近公共祖先

以P3379 【模板】最近公共祖先为例

倍增写法

注意 必须将根节点的dep赋值为 $1$，否则在查询根节点和另一个节点的lca时会有问题
最好把倍增部分放到dfs中进行，若要在主函数进行，必须先枚举指数 $k$

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
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e6;
int head[N], nxt[N], to[N], num = 1;
void add(int x, int y) {
    num++;
    to[num] = y;
    nxt[num] = head[x];
    head[x] = num;
}
int fa[N][30], dep[N];
void dfs(int u) {
    for (int i = 1; i <= 25; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa[u][0]) continue;
        fa[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 25; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    }
    if (x == y) return x;
    for (int i = 25; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dep[s] = 1;
    dfs(s);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        int l[3];
        cout << lca(a, b) << endl;
    }
    return 0;
}

树链剖分

沿着重链跳即可

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
#include <iostream>
using namespace std;
const int N=500005;
int head[N],nxt[N*2],to[N*2];
int size[N],dep[N],fa[N],son[N],top[N];
int num=0;
void add(int f,int t){
	num++;
	to[num]=t;
	nxt[num]=head[f];
	head[f]=num;
}
void dfs1(int u,int f){
	size[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==f) continue;
		dep[v]=dep[u]+1;
		fa[v]=u;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[son[u]]){
			son[u]=v;
		}
	}
}
void dfs2(int u,int t) {
	top[u]=t;
	if(!son[u]){
		return;
	}
	dfs2(son[u],t);
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v!=fa[u]){
			if(v!=son[u])dfs2(v,v);
		}
	}
}
int main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dep[s]=1;
	dfs1(s,0);
	dfs2(s,0);
	while(m--){
		int x,y;
		cin>>x>>y;
		while(top[x]!=top[y]){//cout<<1;
			if(dep[top[x]]>dep[top[y]]){
				x=fa[top[x]];
			}else{
				y=fa[top[y]];
			}
		}
		cout<<(dep[x]<dep[y]?x:y)<<endl;
	}
	return 0;
}

tarjan

先vis设为 $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
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6 + 6;
int head[N], nxt[N], to[N], num = 1;
void add(int x, int y) {
    num++;
    to[num] = y;
    nxt[num] = head[x];
    head[x] = num;
}
int fa[N];
int fi(int x) {
    if (fa[x] != x) return fa[x] = fi(fa[x]);
    return fa[x];
}
struct qu {
    int a, b, ans;
} qs[N];
vector<int> que[N];
int n, m, s;
int vis[N];
void tarjan(int u) {
    vis[u]++;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (vis[v]) continue;
        tarjan(v);
        fa[fi(v)] = fi(u);
    }
    vis[u]++;
    for (auto i : que[u]) {
        int v;
        if (qs[i].a == u)
            v = qs[i].b;
        else
            v = qs[i].a;
        if (vis[v] == 2 && !qs[i].ans) qs[i].ans = fi(v);
    }
}
int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= m; i++) {
        cin >> qs[i].a >> qs[i].b;
        que[qs[i].a].push_back(i);
        que[qs[i].b].push_back(i);
    }
    tarjan(s);
    for (int i = 1; i <= m; i++) {
        cout << qs[i].ans << endl;
    }
    return 0;
}

习题

洛谷题单