求 LCA 的 Tarjan 算法

这是一个复杂度为 O(n+q)O(n+q) 的离线求 LCA 算法

用 dfs 进行遍历并打 tag

假设遍历到 uu,则已回溯的节点标为 22,遍历到但未回溯的节点(即 uuuu 的祖先)标 11,其余为 00

现在假设 uu 的子树处理完毕,考虑 uu 的处理

询问节点为 (u,v)(u, v)

此时,若 tagv=2\mathrm{tag}_v = 2,则可以保证 vv 向根走遇到的第一个 tag=1\mathrm{tag} = 1 的节点即为 LCA(u,v)\mathrm{LCA}(u,v),可以用反证法证明

若向根走遇到的第一个 tag=1\mathrm{tag} = 1 的节点,记为 wwwLCA(u,v)w \not = \mathrm{LCA}(u,v)

LCA(u,v)\mathrm{LCA}(u,v)pp

显然 ppuu 到根的路径上

ppww 下方,则 tagp1\mathrm{tag}_p \not= 1,但是 pp 又为 uu 的祖先,tag=1\mathrm{tag}=1

矛盾

ppww 上方,根据算法可得 wwvv 的 祖先,又 tagw=1\mathrm{tag}_w = 1wwuu 的祖先,所以 ww 必为 uuvv 的公共祖先,但是 ppww 的祖先

矛盾

证毕

下面的程序复杂度应该没有问题,但是要卡一下常,吸一口氧才能过

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
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

const int N = 500010;

std::vector<int> g[N * 2], query[N], query_id[N];

int tag[N], ans[N], fa[N];

int get(int x) { return (x == fa[x]) ? x : (fa[x] = get(fa[x])); }

void tarjan(int u) {
tag[u] = 1;
for (auto v : g[u]) {
if (tag[v] == 0) {
tarjan(v);
fa[v] = u;
}
}
for (int i = 0; i < query[u].size(); ++i) {
int v = query[u][i];
if (tag[v] == 2) {
ans[query_id[u][i]] = get(v);
}
}
tag[u] = 2;
}

int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
std::ios::sync_with_stdio(false);
cout.tie(0);
int n, m, s;
cin >> n >> m >> s;
fa[1] = 1;
rep(i, 2, n) {
fa[i] = i;
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
rep(i, 1, m) {
int u, v;
cin >> u >> v;
query[u].push_back(v), query_id[u].push_back(i);
query[v].push_back(u), query_id[v].push_back(i);
}
tarjan(s);
rep(i, 1, m) cout << ans[i] << endl;
return 0;
}
作者

Gesrua

发布于

2019-07-14

更新于

2020-11-21

许可协议