<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