Lowest Common Ancestor (LCA)
Lowest Common Ancestor (LCA)
17/12/2019
I. Bài toán
Trả lời nhiều queries của bài toán tìm LCA 2 nodes u, v trong 1 rooted tree.
Lưu ý u, v phải nằm trong 1 cái tree, điều đó đảm bảo every nodes have only 1 parent (aka $2^0$-th parent).
II. Ý tưởng
Có nhiều cách tìm LCA, mình sẽ trình bày cách phổ biến nhất có tên là binary raise (or binary lifting).
Ý tưởng chính:
+ $\ $ Ta dùng ý tưởng quy hoạch động để build được
$\ \ \ \ \ $ $p[i][j]$: node cha thứ $2^j$ của node $i$.
+ $\ $ Mọi số tự nhiên đều có thể phân tích thành tổng các lũy thừa của $2$. Đơn giản đó chính là binary representation của số đó thôi. (cơ bản là do chỉ có 2 hệ số 0, 1).
$\rightarrow$ Mỗi query tốn $O(log\ n)$, precompute tốn $O(n\ log\ n)$.
II. Implementation
1const int N = 1e5+5;
2const int LG = 20;
3int n, tree[N];
4int Lv[N], p[N][LG];
5void dfs(int v){ //assign Lv[root] = 1 before call dfs(root)
6 for(auto u:g[v]){
7 if (Lv[u]) continue;
8 p[u][0] = v; //important!
9 Lv[u] = Lv[v] + 1;
10 dfs(u);
11 }
12}
13void precompute(){
14 for(int j=1; j<LG; j++){
15 for(int i=1; i<=n; i++) {
16 p[i][j] = p[p[i][j-1]][j-1]; //just typical DP technique
17 }
18 }
19}
20int LCA(int u, int v){
21 if (Lv[u] < Lv[v]) swap(u, v);
22 int diff = Lv[u] - Lv[v];
23 for(int i=LG-1; i>=0; i--){
24 if ((1<<i)&diff) { //from u, we jump up (later step shorter than sooner step)
25 u = p[u][i];
26 }
27 }
28 //after that, Lv[u] == Lv[v]
29 if (u == v) return u;
30 for(int i=LG-1; i>=0; i--){
31 if (p[u][i] != p[v][i]) { //from lca(u, v) go up, it's all the same
32 u = p[u][i];
33 v = p[v][i];
34 }
35 }
36 //now: u, v locate is the child of lca(u, v);
37 return p[u][0]; //=p[v][0]
38}
39int main() //use
40{
41 Lv[1] = 1; //don't miss it
42 dfs(1); //take 1 to be root of the tree.
43 precompute();
44 while(queries--){
45 int lca = LCA(u, v);
46 }
47}
Bên trên là dạng cổ điển tìm LCA, có nhiều bài toán vận dụng ý tưởng đó, ta có thể tính theo cạnh lớn nhất ở path từ u->v, cái ý tưởng ‘binary raise’ có thể giúp ta carry cái mình cần trong 1 matrix $O(n\ log\ n)$ như $p[N][LG]$
Ngoài ra, mình còn thấy có kiểu jump theo step khá tổng quát như sau:
1int jump(int v, int step){
2 for(int i=LG-1; i>=0; i--){
3 if ((1<<i)&step) {
4 v = p[v][i];
5 }
6 }
7 return v;
8}
Và timein, timeout come to rescue để xác định ADN của thằng u có phải là hậu bối của v không như sau.
1bool isAncestor(int u, int v){
2 return tin[u] > tin[v] && tout[u] < tout[v];
3}
4// I prefer set tin and tout like that
5int timer = 0;
6void dfs(int v){
7 tin = timer++;
8 //do stuff
9 tout = timer++;
10}