本节介绍Tarjan算法求LCA的原理和过程。

        LCA已经在之前的日志中提及，当时使用的倍增算法，见这篇文章。
        Tarjan算法是基于并查集求LCA的离线算法。所谓离线，是指读入所有的查询，然后在一次遍历中处理所有查询并得出结果。这种算法不能边读入查询边计算，遍历完成后不能再处理额外的查询。
        Tarjan算法巧妙地利用了树的遍历规律。在树的DFS遍历中，容易发现当我们在遍历一棵树时，如果它的所有子树结点尚未被完全访问，这棵子树的根结点状态是不能更新的。也就是说，只有访问了所有子结点后，该结点的状态才可以更新。Tarjan算法便是利用了这一点。
        Tarjan算法可以描述如下，从根结点开始：

  1. 遍历所有子结点，每遍历完一个，将子结点合并到该结点上（并查集操作），并标记该结点已被访问。
  2. 遍历完成后，找到与该结点有关的所有查询。如果另一个结点v已经被访问，那么这个查询的结果就是find(v)（并查集操作），否则忽略。

        算法正确性是易于理解的。对于一个刚刚完成访问操作的结点，我们找到所有与之相关的查询。如果此时另一个结点也被访问了，可以肯定两个结点在一个子树下，并且这棵子树的访问操作没有完全完成（毕竟我们正在访问的就是它的一个子结点或者孙子结点等等），根结点（也就是LCA）的并查集属性（也就是father）尚未被更改（如前文所说，只有遍历完所有子结点才能更改）。注意到每访问一个子结点后我们都将其与父结点合并，那么LCA就可以通过find()函数向上追溯的方法找到了，期间可以使用并查集的路径压缩算法。
        Tarjan算法中的并查集算法与普通的并查集几乎完全相同，唯一不同点是合并的顺序。普通并查集合并两个点时合并顺序是随意的，但是Tarjan算法中必须是子结点合并到父结点上。其实这里的并查集可以看做以前树上常用的记录父结点关系的parent数组。

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
#include<iostream>
#include<cstdio>

#define MAX (500000+5)
using namespace std;
struct {
    int to, next;
} edge[MAX * 2];
struct {//将查询视为图
    int to, next, r;//r是查询编号
} qEdge[MAX * 2];
int head[MAX], qHead[MAX], father[MAX], ans[MAX] = {0}, cnt = 1, qCnt = 1, n, m, root;
bool vis[MAX] = {false};

inline int read() {
    char e = getchar();
    while (e < '0' || e > '9')e = getchar();
    int s = 0;
    while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = getchar();
    return s;
}

inline void add(int x, int y) {//树的图构建
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void qAdd(int x, int y, int r) {//查询关系图构建
    qEdge[qCnt].to = y, qEdge[qCnt].next = qHead[x], qEdge[qCnt].r = r, qHead[x] = qCnt++;
}

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

inline void merge(int x, int y) {//x合并到它的父结点y上!
    father[x] = find(y);//就是father[find(x)]=find(y)，因为find(x)就是x
    //father[y]=find(x)是错的
}

void Tarjan(int x, int fa) {
    for (int i = head[x]; i != -1; i = edge[i].next) {//访问所有子结点
        if (edge[i].to != fa) Tarjan(edge[i].to, x), merge(edge[i].to, x), vis[edge[i].to] = true;
    }
    for (int i = qHead[x]; i != -1; i = qEdge[i].next) {//找到所有相关查询
        if (!ans[qEdge[i].r] && vis[qEdge[i].to])ans[qEdge[i].r] = find(qEdge[i].to);
    }
}

int main() {
    int x, y;
    n = read(), m = read(), root = read();
    for (int i = 1; i <= n; i++)qHead[i] = head[i] = -1, father[i] = i;
    for (int i = 1; i < n; i++)x = read(), y = read(), add(x, y), add(y, x);
    for (int i = 0; i < m; i++)x = read(), y = read(), qAdd(x, y, i), qAdd(y, x, i);
    vis[root] = true, Tarjan(root, 0);
    for (int i = 0; i < m; i++)cout << ans[i] << endl;
    return 0;
}