owned this note
owned this note
Published
Linked with GitHub
---
tags: 2023-i2cp
type: slide
slideOptions:
transition: fade;
---
<style>
.reveal .slides {
text-align: left;
font-size:28px;
}
</style>
# LCA and Euler Tour Technique
Introduction to Competitive Programming
4/5
----
- 最近共同祖先(Lowest Common Ancestor)
- 樹上路徑詢問
- 樹上差分
- 樹壓平(Euler Tour Technique)
----
## 最近共同祖先
### Lowest Common Ancestor (LCA)
給定一顆**有根樹**，多筆詢問
每次給你兩個點 $u, v$，問同時為兩個點的祖先中，深度最深的點是誰
<div style="position: absolute; right: 10%;">
</div>
以右圖為例，根節點為1:
5 跟 6 的 lca 為 2
1 跟 7 的 lca 為 1
7 跟 8 的 lca 為 4
5 跟 4 的 lca 為 1
----
## 作法
定義 k 倍祖先為節點往根節點方向走 k 步的節點，超過根節點則設為根節點
### 預處理
對於每個節點，儲存 $2^0、2^1、2^2...、2^{\lfloor \log N \rfloor }$倍祖先
<div style="position: absolute; right: 10%;">
</div>
<div style="font-size:25px;position: absolute; right: 58%;">
| |$2^0$倍|$2^1$倍|$2^2$倍|$2^3$倍|
| ------ | ---- | ---- | ---- | ---- |
| node1 | 1 | 1 | 1 | 1 |
| node2 | 1 | 1 | 1 | 1 |
| node3 | 1 | 1 | 1 | 1 |
| node4 | 3 | 1 | 1 | 1 |
| ... | | | | |
| node8 | 4 | 3 | 1 | 1 |
</div>
----
### 預處理
儲存每個節點 $2^0、2^1、2^2...、2^{\lfloor \log N \rfloor}$倍祖先
$2^0$ 倍祖先為父節點
$2^1$ 倍祖先為 $2^0$ 倍祖先的 $2^0$ 倍祖先
$2^2$ 倍祖先為 $2^1$ 倍祖先的 $2^1$ 倍祖先
...
$2^k$ 倍祖先為 $2^{k-1}$ 倍祖先的 $2^{k-1}$ 倍祖先
可以先 dfs 一遍，紀錄每個點的父節點( $2^0$ 倍祖先)是誰 而根節點的 $2^0$ 倍祖先為自己
----
### 預處理
$2^k$ 倍祖先為 $2^{k-1}$ 倍祖先的 $2^{k-1}$ 倍祖先
用 dfs 找到所有節點的 $2^0$ 倍祖先之後，即可計算出 $2^1$ 倍祖先
以此類推可以再算出 $2^2, 2^3, ..., 2^{\lfloor \log N \rfloor}$ 倍祖先
```cpp=
int anc[N][lgN+1];
for(int i=1;i<=lgN;i++){
for(int u=0;u<N;u++){
//點 u 的 2^i 倍祖先即為 u 的 2^(i-1) 倍祖先的 2^(i-1) 倍祖先
anc[u][i] = anc[anc[u][i-1]][i-1];
}
}
```
$\lfloor \log N \rfloor$ 可以用C++ 內建函式 __lg(n) 求
----
## 時間戳記
紀錄每個點被走到以及離開的時間順序
如果其中兩點 $u, v$ 為祖先後代關係，
則祖先節點 $u$ 進去時間會早於後代 $v$，且離開時間會晚於後代
紀錄時間戳記即可判斷兩者是否為**祖先後代關係**
而可以在 dfs 時順便紀錄時間戳記
----
## 詢問
對於詢問兩點 $u, v$ 的最近共同祖先，可以分為三種 case:
<div style="position: absolute; right: -5%;">
</div>
1. 點 $u$ 為點 $v$ 的祖先
2. 點 $v$ 為點 $u$ 的祖先
3. 兩者互不為彼此的祖先
前兩種 case 可以直接透過時間戳記判斷
並且答案即為祖先節點的那個
case1: lca(1, 7) = 1
case2: lca(6, 2) = 2
第三種 case 我們可以用 Binary Lifting Approach 得到答案
----
## Binary Lifting Approach
當點 $u, v$ 兩者互不為彼此的祖先的時候
若彼此都不是祖先關係，則我們找出 $u$ 的祖先中最靠近根節點的非 $v$ 的祖先
<div style="position: absolute; right: -5%;">
</div>
以點 $7, 2$ 為例，詢問兩點的 lca
我們先找到點 $7$ 往上不為點 $2$ 的點中最上面的
為點 $3$
如果直接暴力找最差 $O(N)$
而這時就用到剛剛建好的倍增祖先表
----
## Binary Lifting Approach
點 $u$ 往上移動，移動到不為點 $v$ 的祖先的點中最上面的那個
嘗試從移動到點 $u$ 的 $2^{\lfloor lgN \rfloor}$ 倍祖先，判斷是不是點 $v$ 的祖先，如果不是則移動上去
接著就 $2^{\lfloor \log N \rfloor -1},..., 2^1, 2^0$ 倍祖先嘗試移動
<div style="position: absolute; right: -15%;">
</div>
以點 $7, 2$ 為例
判斷節點 7 的 $2^3$ 倍祖先是否為點 2 的祖先(是)
判斷 $2^2$ 倍祖先是否為點 2 的祖先(是)
判斷 $2^1$ 倍祖先是否為點 2 的祖先(否)
則移動到 $2^1$ 倍祖先(節點3)
判斷 節點3 的 $2^0$ 倍祖先是否為點 2 的祖先(是)
最後找到節點 3，父節點(節點1)即為答案
----
如果我們要找的距離為 9，則可以透過 Binary Lifting Approach
往上移動 $2^3 + 2^0 = 9$
最差情況為以下情況 query(8, 2)
從節點 8 往上跳到節點 3 (距離為 n-2)
----
紀錄 $2^0, 2^1, 2^2,..., 2^{\lfloor \log N \rfloor}$ 的所有倍數祖先
最差我們需要移動 N-2 步
$\sum\limits_{i=0}^{\lfloor \log N \rfloor} 2^i > N-2$
因此一定可以走到
----
## 詢問
```cpp=
int getLca(int u, int v){
if(isAncestor(u, v)) return u; // 如果 u 為 v 的祖先則 lca 為 u
if(isAncestor(v, u)) return v; // 如果 v 為 u 的祖先則 lca 為 u
for(int i=lgN;i>=0;i--){ // 判斷 2^lgN, 2^(lgN-1),...2^1, 2^0 倍祖先
if(!isAncestor(anc[u][i], v)) // 如果 2^i 倍祖先不是 v 的祖先
u = anc[u][i]; // 則往上移動
}
return anc[u][0]; // 回傳此點的父節點即為答案
}
```
----
## 複雜度
### 預處理
每個節點建 $2^0$倍祖先，$2^1$倍祖先，$2^2$倍祖先，...，$2^{\lfloor \log N \rfloor}$倍祖先
總共$N\log N$個，每個建立為 $O(1)$
複雜度為 $O(N\log N)$
### 詢問
每筆詢問則是在樹上二分搜，找非共同祖先中最靠近根節點的節點
每次詢問最差$O(\log N)$
### 總複雜度
$O(N\log N + Q\log N)$
----
## 樹上路徑詢問
給一棵 $N$ 個節點的樹，每個邊上有權重 $w_i$
$Q$ 筆詢問，每次問節點 $u$ 到節點 $v$ 的路徑長度
- $1\le N, Q\le 2\cdot 10^5$
- $1\le w_i\le 10^9$
----
## [求樹上兩點的距離](https://cses.fi/problemset/task/1135)
<div style="position: absolute; right: 5%;">
</div>
多筆詢問，每次求樹上兩點 $(u, v)$的距離
dist(5, 8) = 5
dist(7, 7) = 0
dist(6, 1) = 2
求出兩點距離等價於
dist(u, v) = dist(u, lca) + dist(lca, v)
----
## 求出節點到 lca 的距離
可以用倍增表
在紀錄節點的 $k$ 倍祖先時，順便紀錄到 $k$ 倍祖先的距離
到 1 倍祖先距離 = 與父節點連的邊權重
到 2 倍祖先距離 = 到 1 倍祖先的距離 + 1 倍祖先的 1 倍祖先距離總和
到 4 倍祖先距離 = 到 2 倍祖先的距離 + 2 倍祖先的 2 倍祖先距離總和
...
----
因此可以得到每個節點到 $2^0, 2^1,..., 2^{\lfloor \log N \rfloor}$ 倍祖先的距離
```cpp=
void build(int x, int f, int d){ // 傳入節點x、父節點 f、以及 x 到父節點的距離 d
for(int i = 0; i < lgN; i++){
anc[x][i] = f;
dis[x][i] = d;
f = anc[f][i];
d += dis[f][i]; // dis(x, 2^(i+1) 倍祖先) = dis(x, 2^i 倍祖先) +
// dis(2^i 倍祖先, 2^i 倍組先的 2^i 倍祖先)
}
}
```
----
### 倍增法求總和
dis(u, v) = dis(u, lca) + dis(v, lca)
從 u, v 分別往上跳到 lca 為止，過程中經過的節點累積總和
```cpp=
ll queryDis(int x, int y){
int lca = getLca(x, y);
ll ret = 0;
for(int i = lgN; i >= 0; i--){
// from x to lca
if(!isAncestor(anc[x][i], lca)){
ret += dis[x][i]; // 把 x 到 2^i 倍祖先的路徑長度加入答案
x = anc[x][i]; // 跳到 x 的 2^i 倍祖先
}
// from y to lca
if(!isAncestor(anc[y][i], lca)){
ret += dis[y][i]; // 把 y 到 2^i 倍祖先的路徑長度加入答案
y = anc[y][i]; // 跳到 y 的 2^i 倍祖先
}
}
if(x != lca) ret += dis[x][0]; // 如果 x 本來就是 lca 不用加
if(y != lca) ret += dis[y][0]; // 如果 y 本來就是 lca 不用加
return ret;
}
```
---
### 樹上路徑詢問
若題目為求出樹上兩點間的資訊(如距離、路徑上最小/大值)等問題，並且有結合律
都可以透過建立倍增表後，使用 Binary Lifting Approach
在複雜度 $O(N\log N + Q\log N)$ 解決
----
## [次小生成樹](https://codeforces.com/group/dnlUA4rsoS/contest/379764/problem/E)
### Second Best Minimum Spanning Tree
給你一張圖，請選出一些邊使得整張圖連通，並輸出次小的權重和。
$N, M \le 2 \cdot 10^5$
以上圖為例
最小生成樹為 1 + 2 + 4 = 7
次小為 1 + 3 + 4 = 8
----
求出次小生成樹，即為把一條原本不在最小生成樹上的邊加進來
加進來後圖會形成環，把環上一條邊去掉才會變樹，
如果要最小則把除了新的那條邊以外最大那條邊去掉
----
## 作法
先求出 MST 之後，窮舉每條不在 MST 上的邊放上去，而會形成環
把環上除了新的邊中權重最大的邊移除，判斷是否為答案
上圖綠色邊為MST上的邊，而我們可以嘗試把每條不在樹上的放上去
放 (1, 4) 形成環，把環上權重最大的移除 (1, 2)
權重為 7(原本的MST權重) + 3(新增的邊) - 2(環上權重最大的邊) = 8
放 (3, 4) 形成環，把環上權重最大的移除 (1, 3)
權重為 7(原本的MST權重) + 8(新增的邊) - 4(環上權重最大的邊) = 11
----
## 找出環上權重最大的邊
如果直接暴力找，複雜度 $O(MN)$
因此有一個好的方法，使得找最大邊的複雜度降低
----
## LCA
如果對於 MST 去建 LCA
並且建出每個點到 $2^0, 2^1,...,2^{\lfloor \log N \rfloor}$ 倍祖先路徑上最大權重的邊
每次找環上權重最大的邊即為
max(點 $u$ 到 lca 路徑最大值, 點 $v$ 到 lca 路徑最大值)
每次只需要 $O(\log N)$ 即可找到環上最大權重!
複雜度 $O(N\log N + M\log N)$
---
## 樹上差分
----
### 回顧序列上差分
給長度為 $N$ 的序列，一開始每個節點上權重為 0
$Q$ 筆操作，每次把區間 $l$ 到 $r$ 加值 1，也就是區間加值
最後輸出每個位置的值
- $1\le N, Q\le 2\cdot 10^5$
----
在序列上區間只需在陣列上 l 的位置 +1，r 的位置 -1
最後再從頭開始開始累積前綴和
```cpp=
void add(int l, int r){
tag[l] ++;
tag[r+1] --;
}
void solve(){
ll tot = 0;
for(int i = 1; i <= n; i++){
tot += tag[i];
cout << tot << " \n"[i==n];
}
}
```
----
## 例題
給一棵 $N$ 個節點的樹，一開始每個節點上權重為 0
$Q$ 筆操作，每次把節點 $u$ 到 $v$ 的路徑上所有點權重 +1
最後輸出每個點的權重
- $1\le N, Q\le 2\cdot 10^5$
----
## 有根樹的性質
1. 樹上所有點對的路徑都是唯一的
2. 每個節點的父節點都是唯一的
有這個兩個性質即可在樹上差分
----
對於一條要加值的路徑 $(u, v)$，先拆成兩段，(u->lca) 和 (v->lca)
兩段路徑分別處理，路徑我們要從下往上差分，因為父節點是唯一的
如果從 lca 往下差分，由於有很多子節點，每次往下差分會不知道往哪邊累加
----
拆成兩段
第一段為節點 $u$ 到 lca 的路徑
第二段為節點 $v$ 到 lca 的前一格的路徑
以 9 ~ 12 的路徑為例，拆成 (9, 7) 和 (10, 12)
----
第一段: tag[u] += 1, tag[f[lca]] -= 1
第二段: tag[v] += 1, tag[lca] -= 1
以 9 ~ 12 的路徑為例，拆成 (9, 7) 和 (10, 12)
----
### 加值程式碼
第一段: tag[u] += 1, tag[f[lca]] -= 1
第二段: tag[v] += 1, tag[lca] -= 1
```cpp=
void PathAdd(int u, int v){
int lca = getLca(u, v);
tag[u]++, tag[v]++;
tag[lca]--;
if(lca != root) tag[f[lca]]--;
}
```
----
加值完之後，從根節點 dfs 一遍，每次把當前節點的差分值加給父節點
 $\to$ 
----
計算所有子樹的差分值，累積給自己加上自己的 tag 即為自己的差分值
最後再把自己的差分值回傳給父節點用
```cpp=
ll dfs(int x, int f){
ll diff = tag[x];
for(int i:edge[x]){
if(i != f){
diff += dfs(i, x);
}
}
return ans[x] = diff;
}
```
----
### 複雜度
$Q$ 筆操作，每次需要找到 LCA 為 $O(\log N)$
最後再 DFS 一遍 $O(N)$
總複雜度為 $O(Q\log N + N)$
----
可以思考如果加值在邊上要怎麼做
---
## 樹壓平
### Euler Tour Technique
<div style="font-size:25px">
[子樹詢問、修改](https://cses.fi/problemset/task/1137)
EX：有一棵樹 $N (1\le N \le 2 \cdot 10^5)$個節點，節點上有權重，
兩種操作
1. 詢問某個點的子樹權重總和
2. 修改某個點的值
</div>
----
作法
$Q$ 筆詢問，每次 $O(N)$ 修改
複雜度 $O(QN)$ ...太慢了
因此我們要把樹壓平
----
紀錄每個點dfs時進入的時間
node | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
-- | - | - | - | - | - | - | - | - |
dfs time| 1 | 2 | 8 | 3 | 4 | 5 | 6 | 7 |
----
<div style="font-size:25px;">
而每個點的子樹，dfs 順序必定會是連續的
EX:
- 5 的子樹 dfs 順序為 4-7 之間
- 2 的子樹 dfs 順序為 2-7 之間
- 1 的子樹 dfs 順序為 1-8 之間
因此我們把每個點的子樹區間記錄起來，
就可以用線段樹之類的資料結構維護子樹區間
</div>
----
<div style="font-size:25px; text-align:left; margin-left:31%">
EX:
- 修改 5 的子樹修改區間 4-7
- 詢問 2 的子樹詢問區間 2-7
</div>
----
紀錄子樹區間
```cpp=
int ti=0;
vector<pair<int,int>> dfsTime(n);
int dfs(int x,int f){
dfsTime[x].first=dfsTime[x].second=ti++;
for(auto i:edge[x]){
if(i==f) continue;
dfsTime[x].second=max(dfsTime[x].second,
dfs(i,x)); //紀錄最右界
}
return dfsTime[x].second;
}
```
----
用資料結構(線段樹等)維護後，單次詢問/修改的複雜度
就從原本的 $O(N)$ 降成 O$(\log N)$
```cpp=
tree.update(dfsTime[x].first, ddfsTime[x].second);
```
----
### 用樹壓平求LCA
| time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |
| ----- | - | - | - | - | - | - | - | - | - | - | - | - | - |
| node | A | B | C | D | C | E | F | E | C | B | A | G | A |
| depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 |
----
LCA(D,F) = C
| time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |
| ----- | - | - | - | - | - | - | - | - | - | - | - | - | - |
| node | A | B | C |[D | C | E | F]| E | C | B | A | G | A |
| depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 |
----
求出 u, v 的LCA為區間內的最小深度的點
| time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |
| ----- | - | - | - | - | - | - | - | - | - | - | - | - | - |
| node | A | B | C | D | C | E | F | E | C | B | A | G | A |
| depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 |
----
記錄每個點的進來時間與離開時間
```cpp=
int ti = 0; //時間戳記
void dfs(int x,int f,int d){
dep[ti] = d; //記錄在當下時間點的節點深度
node[ti] = x; //記錄在當下時間點的節點
tin[x] = ti++; //紀錄點x進入時間點
for(auto i:edge[x]){
if(i != f) dfs(i,x,d+1);
}
dep[ti] = d; //記錄在當下時間點的節點深度
node[ti] = x; //記錄在當下時間點的節點
tout[x] = ti++; //紀錄點x離開時間點
}
```
----
因此可以用線段樹等資料結構求LCA
```cpp=
int query(int u, int v){
if(tin[u] > tin[v]) swap(u, v);
return segmentTree.query(tout[u], tin[v]);
}
```
---
### Homework and Practice
deadline: 4/16
link: https://vjudge.net/contest/551157
challenge: https://codeforces.com/gym/102694
Google Drive
Gist
Clipboard
Sign in with Wallet
