<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Tree Algorithm 1 Introduction to Competitive Programming 04/17 ---- - 時間戳記 - 倍增法binary lifting - 最近共同祖先Lowest Common Ancestor - 樹上差分 --- ## 時間戳記 時間戳記是一個用來判斷兩個點是不是有祖孫關係的實用工具，可以通過 $O(n)$ 預處理和 $O(1)$ 的查詢來判斷任意兩個點在樹上的關係。  ---- 用 DFS 從樹根跑過一遍所有點，紀錄「向下進入」的時間點和「向上離開」的時間點。 用一個變數 $t$ 紀錄現在的時間點，每次向下進入一個點就++，向上離開一個點也++。 ----  進入的點是 $in$ ，離開的點是 $out$ ，在每次進入和離開的時候，給予每個點各自的時間戳記。 如果點 u 會是點 v 的祖先，必定滿足： $in[$u$]<in[$v$]$ && $out[$v$]<out[$u$]$ ---- 預處理：用 DFS 給每一個點時間戳記，複雜度： $O(n)$ 。 ```cpp! int timing=1; int in[N],out[N]; void dfs(int u){ in[u] = timing++;//這時進入u for(int nxt : g[u]){//跑過所有孩子 dfs(nxt); } out[u] = timing++;//這時離開u } ``` ---- 查詢：直接查，複雜度 $O(1)$ 。 ```cpp! bool is_ancestor(int u,int v){ return ( in[u] < in[v] && out[v] < out[u] ); } ``` 回傳 1 代表 u 是 v 的祖先。 注意只有在樹不變動的情況下才能給時間戳記。 如果題目的樹逼你一定要換不同的根，就需要重新給時間戳記！ --- ## 倍增法(binary lifting) ---- ## 什麼是倍增 把大問題 f(x) 透過二進制拆分化簡成 f(1)+f(2)+f(4)...+f(2$^{\lfloor \log x \rfloor}$) 來解決。 舉個例子：快速冪 - 當我們要算 $2^x$ 時，會把 $2^x$ 分解成 $2^0,2^1,...,2^{\lfloor \log x \rfloor -1},2^{\lfloor \log x \rfloor}$ 做加總 當然，這只是倍增法最基本的應用。 ---- 舉一個倍增法經典例子： - 給一個長度為 $n$ 的linked list，你只能知道哪一個點和他的下一個點 - 有 $q$ 筆詢問，每筆詢問給你 $x,k$ ，問你從 $x$ 這個點開始，往右走 $k$ 步會是哪一個點 - $(1 \leq n,q \leq 2 \cdot 10^5)$，$(1 \leq x,k \leq n)$  $x=3,k=4$，會走到點 $2$ $x=1,k=3$，會走到點 $6$ ---- 如何用倍增法解決這題呢？我們要先觀察哪個數字可以分成 $2$ 的冪次加總得到。 由於答案是「從 $x$ 開始往右跳 $k$ 次得到」，那其實可以從 $k$ 下手，把跳躍的次數減少，能有效的降低複雜度。 可以試著把跳 $k$ 次換成$\rightarrow$跳 $1+2+4+....2^{\lfloor \log k \rfloor}$ 次的加總 ex:跳 $23$ 步=跳 $4$ 次 $\rightarrow$ $1+2+4+16$ 步 有效的把跳躍次數從 $O(k)$ 降低成 $O(\log k)$ ---- ex:跳 $23$ 步=跳 $4$ 次 $\rightarrow$ $1+2+4+16$ 步 那要怎麼快速的知道某個點跳了 $1$步、 $2$步、 $4$步、 $16$步會到哪裡呢？ ---- 觀察一下，如果 $a$ 點能跳 $2^{i-1}$ 到達 $b$ 點，且 $b$ 點能跳 $2^{i-1}$ 到達 $c$ 點。 那就可以知道 $a$ 點能跳 $2^{i}$ 到達 $c$ 點。  ---- 根據這個關係，可以建出一個二維表格(倍增表)： 定義 $jump[now][i]$ 為 $now$ 這個點跳了 $2^i$ 步會到哪裡  以上圖為例子： $jump[a][i-1]=b$ $jump[b][i-1]=c$ $jump[a][i] = jump[jump[a][i-1]][i-1] =c$ ---- 初始化，記錄每個點往右走 $1$($2^0$) 步到誰 ```cpp! int jump[N][logN];//n個點 最多跳logn步 void init(int now,int nxt){//now走1步可以走到nxt jump[now][0]=nxt; } ``` ---- 列出轉移式 $jump[now][i]=jump[$ $jump[now][i-1]$ $][i-1]$ 以這個轉移式生出倍增表： ```cpp! int jump[N][logN]; for(int i=1;i<=log2(N);i++){//從跳2^1次枚舉到跳2^logn次 for(int now=1;now<=N;now++){ jump[now][i]=jump[jump[now][i-1]][i-1]; } } ``` ---- 建完倍增表之後要怎麼用它呢？ 我們會設一個變數 $i$ ，從 $2^{\log k}$到$2^0$開始枚舉，如果目前 $2^i$ 步小於等於k步，就往右跳 $2^i$ 步。 ```cpp! int query(int x,int k){ int i=log2(k); while(k){ if(jump[x][i]<=k){ x=jump[x][i]; k-=(1<<i); } i--; } return x;//最後跳到的地方就是答案 } ``` ---- 有了剛剛那張倍增表和以下例子：  這時想要從點 $3$ 跳 $6$ 步，這 $6$ 步會被分成 $2^2+2^1$ 步，分成以下步驟 1. 從 $3$ 跳 $2^2$ 步，到達 $jump[3][2]=2$ 2. 從 $2$ 跳 $2^1$ 步，到達 $jump[2][1]=5$ 3. 走到 $5$ 了 :D 一次查詢做完會是 $O(\log n)$ ---- 倍增法還可以解決靜態 RMQ 問題，像是問你從點 $x$ 開始走 $k$ 格，所有經過的點最小的點編號是多少？ 這時除了開一個 $jump$ 二維陣列維護能跳到哪以外，還要另一個二維陣列維護區間的最小值: 定義 $mn[now][i]$為從 $now$ 這個點到 $now+2^i$ 這個點之間的最小值。 ----  想要查詢點 $3$ 到 跳了 $6$ 步的點之間的最小點編號，這 $6$ 步會被分成 $2^2+2^1$ 步 答案為 $min($ $mn[3][2],$ $mn[2][1]$ $)$ ---- ## 樹上倍增 延續剛剛跳 $\log k$ 次的想法套用到樹上就叫樹上倍增 通常會要你求某個點往上跳 $k$ 步會到哪裡 ---- 特別的是，因為是在樹上，往上跳的點一定是原本的點的祖先。 如果 $a$ 這個點往上跳 $2^i$ 步得到 $b$ ，可以說 $b$ 是 $a$ 的 $2^i$倍祖先。  ex: 上圖 $a$ 的 $4$ 倍祖先是 $b$ ， $a$ 的 $1$ 倍祖先是 $c$ ---- 實作的概念一樣，只是會先從根節點跑一遍 DFS 得到誰是誰的父親。 ```cpp! int anc[N][logN]; void dfs(int now,int fa){//現在的點、父節點 anc[now][0]=fa;//now的0倍祖先是pre for(auto i:v[now]){ if(i==fa)continue; dfs(i,now); } } ``` ---- 再去建倍增表 ```cpp! for(int i=1;i<=log2(N);i++){ for(int now=1;now<=N;now++){ anc[now][i]=anc[anc[now][i-1]][i-1]; } } ``` 在接下來的課程中，這個技巧很常用到:D --- ## 最近共同祖先Lowest Common Ancestor 簡稱LCA  ---- ## 定義最低共同祖先 對於樹上的點 $x$ ,點 $y$ ，有一個點 $w$ 他同時為點 $x$ 和點 $y$ 的祖先並且點 $w$ 在樹上的深度為最低，點 $w$ 就會是 $x$ 和 $y$ 的 LCA 。 通常題目會給你點 $x$ ,點 $y$ ，問你 LCA 是誰 <div style="position: absolute; right: 10%;">  </div> 以右圖為例，根節點為 1 : 5 跟 6 的 LCA 為 2 3 跟 7 的 LCA 為 3 6 跟 2 的 LCA 為 2 5 跟 4 的 LCA 為 1 ---- 不難發現我們可以用三種情況來討論兩個點 $(x,y)$ 的 LCA 是誰: <div style="position: absolute; right: 10%;">  </div> 1.$x$ 是 $y$ 的祖先，ex : LCA$(3,7)=3$ 2.$y$ 是 $x$ 的祖先，ex : LCA$(6,2)=2$ 3.其他情況，ex : LCA$(5,4)=1$ ---- 顯然第一和第二種情況可以利用時間戳記來判斷是不是互相為祖孫關係。 如果是 $x$ 是 $y$ 的祖先的話，顯然 LCA$(x,y)=x$ ，反之亦然。 <center>  LCA$(3,7)=3$ </center> ---- 至於第三種情況就需要剛剛所學到的倍增法&時間戳記來解決 <div style="position: absolute; right: -5%;">  </div> 找 LCA 的策略是，從 $x$ 或 $y$ 一直往上跳，跳到 LCA 下 方的點 $u$，再查點 $u$ 的父節點，就是LCA了。 在做查詢之前要先建出整棵樹的倍增表。 一開始會查 $x$ 的 $2^{\lfloor \log n \rfloor}$ 倍祖先，並利用時間戳記 判斷它是不是 $y$ 的祖先，如果不是就將 $x$ 往上跳 到 $2^{\lfloor \log n \rfloor}$ 倍祖先。 接下來就是按照$2^{\lfloor \log n \rfloor -1}$,...$2^2$,$2^1$,$2^0$倍祖先的順序 做一樣的事情，最後必定會跳到點 $u$ 。 以右圖舉例 ---- <center>  </center> 我們會從 $x$ 的 $2^{\lfloor \log n \rfloor}$ 倍祖先開始判斷，可以發現 $2^{\lfloor \log n \rfloor}$ 到 $2^2$ 倍祖先都會是 $y$ 的祖先，所以不跳。 ---- <center>  </center> 再來是 $2^1$ 倍祖先，由於 $2^1$ 倍祖先不是 $y$ 的祖先， $x$ 就會跳到 $2^1$ 倍祖先。 ---- <center>  </center> 最後是 $2^0$ 倍祖先，由於 $2^0$ 倍祖先不是 $y$ 的祖先， $x$ 就會跳到 $2^0$ 倍祖先。 ---- <center>  </center> 這時 $x=u$( LCA 下方的點) ，再查 $x$ 的父節點是誰就行了。 ---- ## 實作： 在寫這個之前要先把時間戳記和倍增表建好。 ```cpp! int getlca(int x, int y){ if(is_ancestor(x, y))return x; // 如果 u 為 v 的祖先則 lca 為 u if(is_ancestor(y, x))return y; // 如果 v 為 u 的祖先則 lca 為 u for(int i=logN;i>=0;i--){ // 判斷 2^logN, 2^(logN-1),...2^1, 2^0 倍祖先 if(!is_ancestor(anc[x][i], y)) // 如果 2^i 倍祖先不是 v 的祖先 x = anc[x][i]; // 則往上移動 } return anc[x][0]; // 回傳此點的父節點即為答案 } ``` ---- ## 複雜度 首先要預處理每個點的 $2^{\lfloor \log n \rfloor }$,$2^{\lfloor \log n \rfloor -1}$,...$2^2$,$2^1$,$2^0$ 倍祖先和時間戳記，複雜度為 $O(n \log n+n)$ 。 有 $q$ 筆詢問 LCA(x,y) ，每次處理查詢 LCA 最多跳 $\log n$ 步，複雜度為 $O(q \log n)$ 。 總體複雜度為 $O(n \log n + q \log n)$ ---- ## 樹上路徑詢問 由 $n$ 個節點和 $n-1$ 條邊所組成的樹，每個邊都有邊權$w_i$，有 $q$ 筆詢問，每筆詢問有 $(x,y)$，問 $x$ 走到 $y$ 的簡單路徑上的邊權總和？ 限制：$(1 \leq n,q \leq 2 \cdot 10^5),( w_i \leq 10^9)$ ---- <div style="position: absolute; right: -5%;">  </div> 設 dis(x,y) 代表 $x$ 到 $y$ 的簡單路徑上的邊權總和，因 為 $x$ 到 $y$ 的簡單路徑上一定會有 LCA 這個點。 所以 dis(x,y) = dis(x,LCA), dis(LCA,y) 以右圖舉例 dis(x,LCA) $= 200+100+20+10$ dis(LCA,y) $= 40+50$ 兩者加起來就是dis(x,y) ---- 在建出 $k$ 倍祖先表的同時，可以再建一個倍增表存距離總和，定義 $dis[x][k]$ 是從 $x$ 這個點到 $k$ 倍祖先的邊權總和。 到 $2^0$ 倍祖先距離 = 與父節點連的邊權重 到 $2^1$ 倍祖先距離 = 到 $2^0$ 倍祖先的距離 + $2^0$ 倍祖先的 $2^0$ 倍祖先距離總和 到 $2^2$ 倍祖先距離 = 到 $2^1$ 倍祖先的距離 + $2^1$ 倍祖先的 $2^1$ 倍祖先距離總和 ... ---- 用DFS初始化 ```cpp! int anc[N][logN]; int dis[N][logN]; void dfs(int now,int fa){ anc[now][0]=fa; for(auto [nxt,val]:v[now]){ if(nxt == fa)continue; dfs(nxt, now); dis[nxt][0]=val; } } ``` ---- 建倍增表 ```cpp! for(int j=1;j<=logN;j++){ for(int i=1;i<=N;i++){ anc[i][j]=anc[anc[i][j-1]][j-1]; dis[i][j]=dis[i][j-1]+dis[anc[i][j-1]][j-1]; } } ``` ---- 查詢部分分成 $2$ 次跳躍，「 $x$ 跳到 LCA 下方的點」和「 $y$ 跳到 LCA 下方的點」 在跳躍過程中順便去查每一次跳躍的 dis ，進行加總就是答案了  由於是兩邊最多跳 $\log n$ 次，所以每次查詢是 $O(\log n)$ ---- ### 結論 若題目為求出樹上兩點間的資訊(如距離、路徑上最小/大值)等問題，並且有結合律 都可以透過建立倍增表後，使用倍增法 在複雜度 $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(點 $x$ 到 lca 路徑最大值, 點 $y$ 到 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,r]$ 操作，會把 $l$ 位置加上 1 ，$r+1$位置加上 -1 。 最後再從頭到尾跑過一遍前綴和。 ```cpp! void add(int l,int r){ tag[l]++; tag[r+1]--; } void solve(){ int tot=0; for(int i=0;i<n;i++){ tot+=tag[i]; cout<<tot<<" "; } } ``` ---- ## 為什麼可以在樹上差分 1. 樹上所有點對的路徑都是唯一的 2. 每個節點的父節點都是唯一的 有這個兩個性質即可在樹上差分 ---- ## 例題 給一棵 $n$ 個節點的樹，一開始每個節點上權重為 0 $q$ 筆操作，每次把節點 $x$ 到 $y$ 的路徑上所有點權重 +1 最後輸出每個點的權重 限制：$(1\le n, q\le 2\cdot 10^5)$ ---- 對於一個要加值的路徑$(x \rightarrow y)$，可以分成兩條路徑$(x \rightarrow lca)$,$(y \rightarrow lca)$進行加值。 這兩條路徑要分兩次加值，接下來我們要決定是「由上往下差分」還是「由下往上差分」哪個比較適合。 ---- 如果由上往下差分的話，由於某個點的子節點可能會有很多個，這時候就沒有辦法確定要往哪個子節點加。 所以我們要由下往上差分，由於每個點的父節點唯一，更新差分的時候會往父節點更新。 ---- 拆成兩段 第一段為節點 $x$ 到 lca 的路徑 第二段為節點 $y$ 到 lca 的前一格的路徑  以 9 ~ 12 的路徑為例，拆成 (9, 7) 和 (10, 12) ---- 第一段: tag[x] += 1, tag[f[lca]] -= 1 第二段: tag[y] += 1, tag[lca] -= 1  以 9 ~ 12 的路徑為例，拆成 (9, 7) 和 (10, 12) ---- ### 加值程式碼 第一段: tag[x] += 1, tag[f[lca]] -= 1 第二段: tag[y] += 1, tag[lca] -= 1 ```cpp! void add(int x,int y){ int lca=getlca(x,y); tag[x]++; tag[y]++; tag[lca]--; if(lca!=root)tag[f[lca]]--; } ``` ---- 加值完之後，從根節點 dfs 一遍，每次把當前節點的差分值加給父節點  $\to$  ---- 對有根樹去dfs，現在的點會加上所有子節點的差分值 ```cpp! int dfs(int now,int fa){ int diff=tag[now]; for(auto nxt:v[now]){ if(nxt==fa)continue; diff+=dfs(nxt,now); } return ans[now]=diff; } ``` ---- 複雜度： $q$ 筆操作，每次需要找到 LCA 為 $O(logn)$ 最後再 DFS 一遍 $O(n)$ 總複雜度為 $O(q \log n + n)$ ---- 加權在邊上也是同個道理，可以想一下怎麼做 --- 作業：[link](https://vjudge.net/contest/621747) deadline：04-28 00:00