最近公共祖先

倍增（略）

离线Tarjan

自己写的简略版

1
int ff[N];
2
int find2(int x){
3
    if(ff[x] != x) ff[x] = find2(ff[x]);
4
    return ff[x];
5
}
6
bool vis[N];
7
void tarjan(int x){
8
    ff[x] = x;
9
    vis[x] = 1;
10
    for(auto v: e[x]){
11
        tarjan(v);
12
        ff[v] = x;
13
    }
14
    for(auto v: qry[x]){
15
        if(vis[v]){
16
            int lca = find2(v); //本次询问x与v的lca
17
        }
18
    }
19
}

oiwiki模板

1
#include <algorithm>
2
#include <iostream>
3
#include <cstring>
4
using namespace std;
5
6
class Edge {
7
public:
8
    int toVertex, fromVertex;
9
    int next;
10
    int LCA;
11
    Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1){};
12
    Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1){};
13
};
14
15
const int MAX = 100;
16
int head[MAX], queryHead[MAX];
17
Edge edge[MAX], queryEdge[MAX];
18
int parent[MAX], visited[MAX];
19
int vertexCount, edgeCount, queryCount;
20
21
void init() {
22
    for (int i = 0; i <= vertexCount; i++) {
23
        parent[i] = i;
24
    }
25
}
26
27
int find(int x) {
28
    if (parent[x] == x) {
29
        return x;
30
    } else {
31
        return find(parent[x]);
32
    }
33
}
34
35
void tarjan(int u) {
36
    parent[u] = u;
37
    visited[u] = 1;
38
39
    for (int i = head[u]; i != -1; i = edge[i].next) {
40
        Edge& e = edge[i];
41
        if (!visited[e.toVertex]) {
42
            tarjan(e.toVertex);
43
            parent[e.toVertex] = u;
44
        }
45
    }
46
47
    for (int i = queryHead[u]; i != -1; i = queryEdge[i].next) {
48
        Edge& e = queryEdge[i];
49
        if (visited[e.toVertex]) {
50
            queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
51
        }
52
    }
53
}
54
55
int main() {
56
    memset(head, 0xff, sizeof(head));
57
    memset(queryHead, 0xff, sizeof(queryHead));
58
59
    cin >> vertexCount >> edgeCount >> queryCount;
60
    int count = 0;
61
    for (int i = 0; i < edgeCount; i++) {
62
        int start = 0, end = 0;
63
        cin >> start >> end;
64
65
        edge[count] = Edge(start, end, head[start]);
66
        head[start] = count;
67
        count++;
68
69
        edge[count] = Edge(end, start, head[end]);
70
        head[end] = count;
71
        count++;
72
    }
73
74
    count = 0;
75
    for (int i = 0; i < queryCount; i++) {
76
        int start = 0, end = 0;
77
        cin >> start >> end;
78
79
        queryEdge[count] = Edge(start, end, queryHead[start]);
80
        queryHead[start] = count;
81
        count++;
82
83
        queryEdge[count] = Edge(end, start, queryHead[end]);
84
        queryHead[end] = count;
85
        count++;
86
    }
87
88
    init();
89
    tarjan(1);
90
91
    for (int i = 0; i < queryCount; i++) {
92
        Edge& e = queryEdge[i * 2];
93
        cout << "(" << e.fromVertex << "," << e.toVertex << ") " << e.LCA << endl;
94
    }
95
96
    return 0;
97
}

用欧拉序列转化为 RMQ 问题

对一棵树进行 DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，可以得到一个长度为 $2n - 1$ 的序列，这个序列被称作这棵树的欧拉序列。

在下文中，把结点 $u$ 在欧拉序列中第一次出现位置编号记为 $pos(u)$（也称作节点 $u$ 的欧拉序），把欧拉序列本身记作 $E[1..2n-1]$ 。

有了欧拉序列，LCA 问题可以在线性时间内转化为 RMQ 问题，即 $pos(LCA(u,v)) = min\{pos(k)|k \in E[pos(u)..pos(v)]\}$。

这个等式不难理解：从 $u$ 走到 $v$ 的过程中一定会经过 $LCA(u,v)$，但不会经过 $LCA(u,v)$ 的祖先。因此，从 $u$ 走到 $v$ 的过程中经过的欧拉序最小的结点就是 $LCA(u,v)$。

用 DFS 计算欧拉序列的时间复杂度是 $O(n)$，且欧拉序列的长度也是 $O(n)$，所以 LCA 问题可以在 $O(n)$ 的时间内转化成等规模的 RMQ 问题。

自己的实现

1
int ff[N];
2
int dfn[N * 2], pos[N * 2], st[20][N * 2], lg[N * 2], dep[N * 2], tot;
3
void dfs(int x, int fa, int d){
4
    ff[x] = fa;
5
    pos[x] = ++tot;
6
    dfn[tot] = x;
7
    dep[tot] = d;
8
    for(auto v: e[x]){
9
        dfs(v, x, d + 1);
10
        dfn[++tot] = x;
11
        dep[tot] = d;
12
    }
13
}
14
void st_pre(){
15
    for(int i = 1; i <= tot; i++) st[0][i] = i;
16
    for(int j = 1; j <= lg[tot]; j++){
17
        for(int i = 1; i + (1 << j) - 1 <= tot; i++){
18
            st[j][i] = dep[st[j - 1][i]] < dep[st[j - 1][i + (1 << (j - 1))]] ? 
19
                st[j - 1][i] : st[j - 1][i + (1 << (j - 1))];
20
        }
21
    }
22
}
23
int get(int x, int y){ //查询x,y两点的lca
24
    int l = pos[x], r = pos[y];
25
    if(l > r) swap(l, r);
26
    int k = lg[r - l + 1];
27
    int res = dep[st[k][l]] < dep[st[k][r - (1 << k) + 1]] ? st[k][l] : st[k][r - (1 << k) + 1];
28
    return dfn[res];
29
}

oiwiki实现

1
int dfn[N << 1], dep[N << 1], dfntot = 0;
2
void dfs(int t, int depth) {
3
    dfn[++dfntot] = t;
4
    pos[t] = dfntot;
5
    dep[dfntot] = depth;
6
    for (int i = head[t]; i; i = side[i].next) {
7
        dfs(side[i].to, t, depth + 1);
8
        dfn[++dfntot] = t;
9
        dep[dfntot] = depth;
10
    }
11
}
12
void st_preprocess() {
13
    lg[0] = -1;  // 预处理 lg 代替库函数 log2 来优化常数
14
    for (int i = 1; i <= (N << 1); ++i) lg[i] = lg[i >> 1] + 1;
15
    for (int i = 1; i <= (N << 1) - 1; ++i) st[0][i] = dfn[i];
16
    for (int i = 1; i <= lg[(N << 1) - 1]; ++i)
17
        for (int j = 1; j + (1 << i) - 1 <= ((N << 1) - 1); ++j)
18
            st[i][j] = dep[st[i - 1][j]] < dep[st[i - 1][j + (1 << i - 1)]
19
                                               ? st[i - 1][j]
20
                                               : st[i - 1][j + (1 << i - 1)];
21
}