<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Tree Algorithm 2 Introduction to Competitive Programming 05/08 ---- - Euler Tour Technique (ETT) - DSU On Tree --- ## Eular Tour Technique (ETT) 中文稱「樹壓平」 用來解決子樹或路徑問題的技巧 ---- ## 複習基本RMQ問題 給你一個長度為 n 的序列，還有 q 筆操作，每次操作有以下兩種: - 查詢區間 [l,r] 的總和 - 把第 x 個數字改成 v $1 \leq n,q \leq 2 \cdot 10^5$ $1 \leq l \leq r \leq n$ $1 \leq x \leq n$ $1 \leq v \leq 10^9$ ---- 如果以前有好好學資料結構會發現這就是一個很裸的資料結構題目，你可以選擇砸線段樹或是 BIT 來解決它。 那如果把 RMQ 搬到樹上呢? ---- ## 看個樹壓平經典例子 : Subtree Query 給你一棵由 n 個點組成的樹，點 1 是根節點，每個點都有各自的點權，有以下 q 筆操作，分成兩種: - 查詢子樹 x 的所有點權總和 - 把第 x 個點的點權改成 v $1 \leq n,q \leq 2 \cdot 10^5$ $1 \leq x \leq n$ $1 \leq v \leq 10^9$ 如果暴力去 query ，複雜度為 $O(nq)$ ，超爛 ---- 顯然在這題做的操作跟裸的資結題大同小異，只是變成了查詢一棵子樹的總和，在沒有明確區間的情況下，那該怎麼查詢呢? 可以試試看生出一些區間，用來進行查詢！ ---- 說到對於每個點要生出各自的區間 可以回想一下上次樹論課所教的時間戳記 透過時間戳記，可以知道每個點會擁有各自的區間 $[in,out]$ ，並透過這個區間去判斷兩點之間是不是有祖孫關係。  ---- 那這些時間戳記所產生的區間是不是也可以當成這題所有操作所需要的區間呢? 答案是可以的! 如何用這些區間解決這題呢? ---- 對一棵樹做完時間戳記以後 首先我們可以開 $2n$ 長度的資料結構 然後進行預處理，把點 $i$ 的點權放在資料結構的 $in[i]$ 上 <center>  </center> ---- 對於一次查詢子樹 $x$ ，會在資料結構上去查區間 $[in[x],out[x]]$ 假設是查詢子樹 3 $\rightarrow$ 會查到 1+5+8+5，剛好是點 3 ,點 4 ,點 7 ,點 8 的總和 <center>  </center> 修改就是直接在資料結構去修改單點 $in[x]$ ，改成 $v$ ---- 預處理 : 得到時間戳記$O(n)$+建資料結構$O(n\log n)$ 每次查詢和修改 : $O(\log n)$ 總複雜度 : $O(n\log n+q\log n)$ ---- 會發現其實資料結構上有些位置根本不會用到，會造成常數太大，可能會有點慢，因此可以考慮修改一下每個點的區間。 只有在進入新的點的時候，時間戳記的變數 ++，離開的時候不會做 ++。 這樣就不會產生多餘的位置 <center>  </center> ---- ```cpp! int timing=0; int in[N],out[N]; void dfs(int u){ in[u] = ++timing;//這時進入u for(int nxt : g[u]){//跑過所有孩子 dfs(nxt); } out[u] = timing;//這時離開u 不會++ } ``` 在離開點的時候不會讓時間戳記增加 ---- 以上可知樹壓平的核心觀念是用 DFS 序把整棵樹搬到一個序列，並且用資料結構對這個序列進行一系列的操作。 看到有題目會問關於子樹的問題，不仿往樹壓平想。 ---- ## 用樹壓平得到LCA 除了倍增法以外，也可以透過樹壓平的方式來取得 LCA ---- 如果對一棵樹去跑 DFS 並把在哪個時間點上經過了哪一個點紀錄成一個序列 <center>  </center> 會得到長度為 $2n-1$ 的序列 ---- 再產生出一個序列為記錄每個時間點所經過的點的深度  ---- 先考慮 LCA(x,y) 不為 x 也不為 y 的例子 假設要查 LCA(5,8) ，會發現要查詢的是最後離開 8 的時間點到首次進入 5 的時間點之間深度最低的點。  ---- 我們會找到最後離開 8 的時間點和首次進入 5 的時間點，對這一個區間去進行查詢  ---- 用資結查詢這個區間深度最低的點，即為 LCA 所以 LCA(5,8) 為點 2  ---- 再來考慮 LCA(x,y)=x 的例子，跟以前教的判斷一模一樣，直接抓兩點的區間來比較！  假設這時 x=2,y=9 可以直接抓「 [首次進入點 2 的時間點,最後離開點 2 的時間點] 」和 「 [首次進入點 9 的時間點,最後離開點 9 的時間點] 」去進行判斷 ---- 先把 Eular tour 和 每個點第一次進入的時間點 以及 每個點最後離開的時間點記起來 ```cpp! vector<int>tour; int timing=0; int in[N],out[N]; void dfs(int u,int fa){ tour.push_back(u);//進入的時間點 in[u]=tour.size()-1; for(auto v:edge[u]){ if(v==fa)continue; dfs(v,u); tour.push_back(u);//走完其中一個孩子 再走回自己 } out[u]=tour.size()-1; } ``` ---- 把tour丟進線段樹然後做查詢 ```cpp! void build(vector<int>&tour){//把tour丟進線段樹初始化 seg.build(tour);//除了tour，還要建每個點的深度 } int query(int x,int y){ if(is_ancster(x,y))return x;//LCA(x,y)=x if(is_ancster(y,x))return y;//LCA(x,y)=y; if(out[y]<in[x])swap(x,y);//如果「y的區間」在「x的區間」的左邊，就交換 int index=seg.query(out[x],in[y]);//取得區間內哪個位置的深度是最低的 return tour[index]; } ``` 複雜度：$O(n\log n)$ ---- ## 休息一下 --- ## 啟發式合併 ### Disjoint Set Union-find on tree, Small to Large 一種非常暴力的算法，通常用於子樹上統計問題 使用小合併到大的順序統計會使得看似很差的複雜度變成好的 ---- ## small to large? 顧名思義是由小的合併到大的概念 想像有 $n$ 個箱子，每個箱子中有不同顏色的球(不同箱子的球顏色可能一樣)，總共有 $q$ 次操作，每次操作有 $(a,b)$ ，會把 $a$ 箱子的球都丟到 $b$ 箱子，接著詢問 $b$ 箱子中有幾種顏色的球。 $(1 \leq n,q \leq 10^5)$ $(1 \leq a,b \leq n)$ ---- 分兩種情況 第一種： $a$箱子.size() > $b$箱子.size() - $a$ 箱子的球的顏色種類比 $b$ 箱子多，可以把 $b$ 箱子所有的球都丟到 $a$ 箱子，把兩個箱子交換`(swap為O(1))`，再把 $a$ 箱子的球清空。 第二種為： $a$箱子.size() < $b$箱子.size() - $a$ 箱子的球的顏色種類比 $b$ 箱子少，直接把 $a$ 箱子所有的球都丟到 $b$ 箱子，再把 $a$ 箱子的球清空。 可以觀察到上面的解法都是小的箱子合併到大的箱子 為什麼要這樣呢？ ---- 如果選擇大的箱子合併到小的箱子，每次最多會花 $O(n)$ 的時間，然而有 $q$ 次操作，複雜度為 $O(nq)$ ，很爛 因此選擇小的箱子合併到大的箱子，做完 $q$ 次操作之後，最多總共進行 $n$ 次移動球的操作，因此均攤會是 $O(n)$ ，因為要維護種類，可能會用 $set$ 來儲存，會多一個 $log$ ，總複雜度 $O(n\log n)$ ---- ### Disjoint Set的路徑壓縮 相信大家寫裸的並查集的時候，80%都是寫路徑壓縮的並查集 畢竟啟發式合併在實作量上比路徑壓縮差很多，而且複雜度也比較差 ($O(nlogn)$) - 路徑壓縮 $\rightarrow$ 複雜度$O(alpha(n))$ ```cpp! int find(int x){ if(f[x]==x)return x; else return f[x]=find(f[x]); } ``` ---- ### 把small to large套用Disjoint Set上 但是以後會遇到有些情況一定要你用啟發式合併，ex:持久化並查集 在寫啟發式合併時，會用到small to large 的概念，以子樹大小來判斷誰合併到誰 ```cpp= void merge(int x, int y){ x = find(x); y = find(y); if(x != y){ if(sz[x] > sz[y]){ sz[x] += sz[y]; f[y] = x; } else{ sz[y] += sz[x]; f[x] = y; } } } ``` 此作法可以讓總複雜度降低至 $O(N \log N)$ 由於此技巧常用於並查集上，應用在其他樹上問題稱做 DSU on Tree ---- ### 啟發式合併 每次合併時，把小的往大的合併 先來看以下兩種極端例子 ---- ### (1) 其中一邊的樹比另一邊大很多， 當小的合併到大的時候複雜度趨近於常數 <div style="position: absolute; right: 70%; top:100%;">  </div> <div style="position: absolute; right: 10%; top:100%;">  </div> ---- ### (2) 當兩邊大小差不多時， 合併的複雜度為 $O(n)$ (n為樹的大小) <div style="position: absolute; right: 70%; top:100%;">  </div> <div style="position: absolute; right: 10%; top:100%;">  </div> ---- 因此可以發現兩種情況中，如果每次合併都是第一種 把小的合併到大的，那[均攤複雜度](https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%91%8A%E5%88%86%E6%9E%90)為 $O(N)$ 但如果每次都是第二種，複雜度會變多少? ---- 答案是 $O(N\log N)$  ---- 因此透過每次小的合併到大的 最差複雜度為 $O(N\log N)$ ```cpp= void merge(int x,int y){ x = find(x), y =find(y); if(sz[x] < sz[y]) swap(x,y); sz[x] +=sz[y]; f[y] = x; } void init(){ //初始化一開始大小都為1 (每群一開始都是獨立一個) for(int i=1;i<=n;i++) sz[i] = 1; for(int i=1;i<=n;i++) f[i] = i; } ``` ---- ### 經典例題 --- [CF 600E](https://codeforces.com/contest/600/problem/E) 給一棵大小為 $n$ $(n\le 10^5)$ 的有根樹 每個節點上都有塗上一種顏色 問分別以每個節點為根的子樹中，出現最多次的顏色其數量為何？ ---- ### 暴力的作法 用 std::map 紀錄每個子樹中每種顏色的數量 把兒子節點統計的數量加進自己的 map 中 ```cpp= int ans[MXN], color[MXN]; map<int, int> dfs(int x, int f){ map<int, int> ret; ret[color[x]] = 1; ans[x] = 1; for(int i : edge[x]){ if(i == f) continue; auto tmp = dfs(i, x); for(auto j : tmp){ ret[j.first] += j.second; ans[x] = max(ans[x], ret[j.first]); } } return ret; } ``` ---- 但這樣太暴力了，如果拿重兒子的 map 當成自己的 好像就可以減少一些時間。 ---- 以下用 map 實作的寫法 運用 swap(map1, map2) 複雜度是 $O(1)$ 的性質 把計算完的重兒子的子樹 map 變成自己的 ```cpp= int ans[MXN], color[MXN], son[MXN]; map<int, int> mp[MXN]; void dfs(int x, int f){ if(son[x]){ dfs(son[x], x); swap(mp[x], mp[son[x]]); ans[x] = ans[son[x]]; } mp[x][color[x]]++; ans[x] = max(ans[x], mp[x][color[x]]); for(int i : edge[x]){ if(i == f || i == son[x]) continue; dfs(i, x); for(auto j : mp[i]){ mp[x][j.first] += j.second; ans[x] = max(ans[x], mp[x][j.first]); } } } ``` ---- 先將子樹的顏色統計完，拿重兒子的 map 當成自己的然後把其他輕兒子加進同一個 map 統計。 如果每個節點顏色都不同，每次合併時 map 的 size 不斷變大 複雜度好像很差 ? 但要怎麼算呢? ---- 和並查集複雜度計算相同， 分成兩種 case : 1. 合併時，合併的子樹大小都是相同 2. 合併時，合併的子樹大小差很大   ---- ## case 1. 合併的子樹大小都是相同  合併子樹時，兩邊大小都相同 ---- 如果樹的形狀趨近於完美二元樹，則樹高為 $\log n$ 而每層要合併的數量為 $\frac{n}{2}$ 因此總共需要合併的次數為 $n\log n$ ---- 而過程中用 map 維護，每次把一個元素加進 map 需要花 $\log n$ 總複雜度 $O(n\log^2 n)$ ---- ## case 2. 每次合併的子樹大小分別為 n-1 和 1  ----  這種 case 從最底下開始處理，如果每次都把小的合併到大的，每次只會把一個元素(小的那棵子樹)加進去 map 中，因此只會加 $n$ 次 使用 map 維護總複雜度為 $O(n\log n)$ ---- 可以發現如果兩堆差異很大時，合併時把小的丟給大的 複雜度會比較好，因此最差的情況為每次合併兩邊大小都差不多的 case 而那種 case 用 map 維護的最差複雜度為 $O(n\log ^2 n)$ ---- 而這種小合併到大的作法為啟發式合併 很多需要合併資訊的題目都可以用啟發式合併的概念 讓看似非常暴力的做法複雜度壓到 $O(n\log n)$ 或者 $O(n\log^2 n)$ --- 如果下個學期的進階程式競賽還無法加選的話，可以等到下學期開學時加簽～  提單link : [link](https://vjudge.net/contest/626081) deadline : 5/19