最低共同祖先 (Lowest Common Ancestor, LCA)
最低共同祖先
在有根樹上任意兩點 ，兩點祖先交集中，深度最深的一個點，稱為兩點的最低共同祖先 (Lowest Common Ancestor, LCA)。
給定一顆有根樹 ( 個點) 和 筆詢問，每筆詢問輸出兩點 的最低共同祖先。
直觀的做法是利用 DFS 尋找兩點的 LCA，每次查詢時間複雜度為 ，這種辦法就容易超過時間限制。
這裡介紹利用倍增法找尋任意兩點的最低共同祖先，這裡用轉態轉移式定義出定義 ：
- 狀態： 代表 的第 層祖先。
- 初始狀態： , 為 的父節點。
- 轉移： 。
和一般的倍增法相同，將算法分成三個步驟。
第一步是 DFS，找出每個點的父節點，以及紀錄進入和離開的時間戳記。
第二步用兩層迴圈算出 剩餘答案。
最後根據 ，用二分搜找出 兩點的最低共同祖先，由於任意兩點 的共同祖先有單調性， 點的所有祖先，在 （包含）之上的祖先是兩點的共同祖先，剩下的只是 的祖先，因此可以用二分搜枚舉 尋找 ，在二分搜過程，時間戳記用於判斷 是否為 的祖先。
DFS 的時間複雜度為 ，計算 剩餘答案的時間複雜度為 ，每次查詢操作的時間複雜度為 ，整題時間複雜度為 。
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 | const int LOG = 20;
int par[N][LOG];
int tin[N], tout[N];
int timer = 0;
void dfs(int v, int p)
{
tin[v] = ++timer;
par[v][0] = p;
for (int it : G[v])
{
if (it != p)
dfs(it, v);
}
tout[v] = ++timer;
}
void Doubling()
{
for (int i = 1; i < N; ++i)
{
for (int j = 1; j < LOG; ++j)
{
par[i][j] = par[par[i][j - 1]][j - 1];
}
}
}
bool anc(int v, int u) { return tin[v] <= tin[u] && tout[u] <= tout[v]; }
int LCA(int v, int u)
{
if (anc(v, u))
return v;
for (int j = LOG - 1; j >= 0; --j)
{
if (!anc(par[v][j], u))
v = par[v][j];
}
return par[v][0];
}
|
找出最低共同祖先的算法，可推廣到找尋 路徑上的資訊，例如：路徑長度、最小（大）權重的邊。
假設 ，把 到 的路徑 可以拆成 和 。
例題練習
Atcoder Beginner Contest 209 D - Collision
給定一棵樹，請問 需要移動偶數步還是奇數步?
練習樹上任兩點之間的距離，令 從 到 的距離， 到 的距離 。
參考程式碼
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 | void dfs(int v, int p)
{
tin[v] = ++timer;
par[v][0] = p;
if (v != p)
dist[v] = dist[p] + 1;
for (int it : G[v])
{
if (it != p)
dfs(it, v);
}
tout[v] = ++timer;
}
int main()
{
int q;
cin >> n >> q;
for (int i = 0, u, v; i < n - 1; ++i)
{
cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
dist[1] = 1;
dfs(1, 1);
Doubling();
for (int i = 0, u, v; i < q; ++i)
{
cin >> u >> v;
int w = LCA(v, u);
int res = (dist[u] + dist[v] - 2 * dist[w]) % 2;
if (res)
cout << "Road\n";
else
cout << "Town\n";
}
}
|
CodeForces 609E - Minimum spanning tree for each edge
給定一張無向圖 ，求包含邊 的生成樹中，權重最小的生成樹為何?
先求出一顆最小生成樹 ，權重和為 ，利用最低共同祖先求出節點 節點 到第 個節點的最大權重路徑，對於每一條邊 ，在 中找到從 到 的最大權重路徑 。答案 （如果 ，）。
UVa 11354 - Bond
給定一張無向帶權圖，有多筆詢問，詢問 之間的路徑最大權重邊權值最小為何。
也就是詢問最小瓶頸樹中， 之間的路徑最大邊重權為何。
這題要先利用 Krusal 求出最小瓶頸樹，接著利用 LCA 求出每個點 到它的第 層祖先的路徑中的最大邊重權。
參考程式碼
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129 | #include <bits/stdc++.h>
using namespace std;
const int N = 50010;
const int INF = 1e9;
const int LOG = 25;
struct Edge
{
int s, t, w;
Edge(){};
Edge(int _s, int _t, int _w) : s(_s), t(_t), w(_w) {}
bool operator<(const Edge &rhs) const { return w < rhs.w; }
};
int n, m, djs[N], depth[N], par[N][LOG], maxcost[N][LOG];
vector<Edge> edges;
vector<int> G[N];
void init()
{
memset(par, -1, sizeof(par));
memset(maxcost, -1, sizeof(maxcost));
edges.clear();
for (int i = 0; i < N; i++)
{
djs[i] = i;
G[i].clear();
}
}
int query(int x) { return (x == djs[x] ? x : djs[x] = query(djs[x])); }
void MST()
{
for (int i = 0; i < m; i++)
{
int fa = query(edges[i].s), fb = query(edges[i].t);
if (fa != fb)
{
djs[fa] = fb;
G[edges[i].s].push_back(i);
G[edges[i].t].push_back(i);
}
}
}
void dfs(int s, int f)
{
depth[s] = depth[f] + 1;
par[s][0] = f;
for (auto i : G[s])
{
// 不知道 s 存在這條邊的哪個位置，用 xor 消除同樣的數字，留下來的就是另外一個點
int t = edges[i].s ^ edges[i].t ^ s;
if (t != f)
{
maxcost[t][0] = edges[i].w;
dfs(t, s);
}
}
}
void preprocess()
{
for (int i = 1; i <= LOG; i++)
for (int j = 1; j <= n; j++)
{
if (par[j][i - 1] == -1 || par[par[j][i - 1]][i - 1] == -1)
continue;
par[j][i] = par[par[j][i - 1]][i - 1];
maxcost[j][i] =
max(maxcost[j][i - 1], maxcost[par[j][i - 1]][i - 1]);
}
}
int solve(int p, int q)
{
if (depth[p] < depth[q])
swap(p, q);
int hibit, ans = -INF;
for (hibit = 1; (1 << hibit) <= depth[p]; ++hibit)// p 的深度以二進位表示的最高位
;
// 把 p,q 兩個點的深度調整到一樣
for (int i = hibit - 1; i >= 0; i--)
if (depth[p] - (1 << i) >= depth[q])
{
ans = max(ans, maxcost[p][i]);
p = par[p][i];
}
if (p == q)
return ans;
// 讓 p,q 變成最低共同祖先的兒子
for (int i = hibit - 1; i >= 0; i--)
{
if (par[p][i] == -1 || par[p][i] == par[q][i])
continue;
ans = max({ans, maxcost[p][i], maxcost[q][i]});
p = par[p][i];
q = par[q][i];
}
return max({ans, maxcost[p][0], maxcost[q][0]});
}
int main()
{
cin.tie(NULL);
for (int ti = 0; cin >> n >> m; ++ti)
{
if (ti) cout << '\n';
init();
for (int i = 0; i < m; i++)
{
int s, t, w;
cin >> s >> t >> w;
edges.emplace_back(s, t, w);
}
sort(edges.begin(), edges.end());
MST();
dfs(1, -1);
preprocess();
int q;
cin >> q;
for (int i = 0; i < q; i++)
{
int x, y;
cin >> x >> y;
cout << solve(x, y) << '\n';
}
}
}
|
CodeForces 1328E - Tree Queries
給定一棵樹， 為樹根，每次詢問給定 個點，有沒有一條路徑和這些點的距離 ?
在 個點中找出最深的點 ，對於每個點 ，判斷 的父節點 是否為 的祖先。
