<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Tree Algorithm 2 Introduction to Competitive Programming 05/15 ---- - Euler Tour Technique (樹壓平) - DSU On Tree --- ## Eular Tour Technique 中文稱「樹壓平」 用來解決子樹或路徑問題的技巧 ---- ## 複習基本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 序把整棵樹搬到一個序列，並且用資料結構對這個序列進行一系列的操作。 看到有題目會問關於子樹的問題，不仿往樹壓平想。 ---- ## 題單題 Path Queries 給你一棵由 n 個點組成的樹，點 1 是根節點，每個點都有各自的點權，有以下 q 筆操作，分成兩種: - 查詢 x 到 root 路徑上所有點的權值總和 - 把第 x 個點的點權改成 v $1 \leq n,q \leq 2 \cdot 10^5$ $1 \leq x \leq n$ $1 \leq v \leq 10^9$ ---- ：啊這題好像跟子樹無關捏 :O ：路徑要怎麼樹壓平做？ ---- 想個問題：一個點 x 的權值會貢獻給哪些人呢？  ---- <center>  </center> 對於一個點 x，他的答案可以貢獻到他自己子樹中的所有點 因此我們可以考慮把樹上單點改值改成一個序列上的區間改值 ---- 點 x 加值 v $\rightarrow$ $[in[v],out[v]]$ 加值 v <center>  </center> 對於點 2 來說，其權值為1，可以貢獻到2,5,6這些點，所以做 [2,4] 的區間加值 ---- 最後會長這樣 <center>  </center> 可以發現，這時候點 x 至 root 的答案剛好會記在 in[x] 裡。 因此可以考慮用線段樹去維護區間上的修改，以及單點查詢。 時間複雜度 $O(n\log n + q\log n)$ ---- 線段樹有點勾八長，那換個做法。 在 BIT 講義有提到如何把[區間加值＋單點查詢](https://hackmd.io/@LeeShoWhaodian/2025-BIT#/2) 放在 BIT 上做掉。 對於區間 [in[x],out[x]] ，考慮去做 in[x] 的加值，以及out[x]+1 的減值，再用 BIT 求前綴和的概念得到單點的值。 常數會比線段樹好很多！ ---- ## 休息一下 --- ## 啟發式合併 ### Disjoint Set Union-find on tree, Small to Large 一種非常暴力的算法，通常用於子樹上統計問題 使用小合併到大的順序統計會使得看似很差的複雜度變成好的 ---- ## 例題 有 $n$ 個箱子，每個箱子中有不同顏色的球(不同箱子的球顏色可能一樣)，總共有 $q$ 次操作，每次操作有 $(a,b)$ ，會把 $a$ 箱子的球都丟到 $b$ 箱子，接著詢問 $b$ 箱子中有幾種顏色的球。 $(1 \leq n,q \leq 10^5)$ $(1 \leq a,b \leq n)$ ---- 如果每次暴力去把 $a$ 箱子的球都丟到 $b$ 箱子，最差會花 $1+...+n-1$ 的時間做完(每次把 size 比較大的箱子丟去另外一邊)，總複雜度 $O(n^2)$，很差。 那反過來呢？把小的丟到大的？ ---- ## small to large? 顧名思義是由小的合併到大的概念，以下分兩種情況 第一種： $a$.size() > $b$.size() - $a$ 箱子的球的顏色種類比 $b$ 箱子多，可以把 $b$ 箱子所有的球都丟到 $a$ 箱子，把兩個箱子交換`(swap為O(1))`，再把 $a$ 箱子的球清空。 第二種為： $a$.size() $\le$ $b$.size() - $a$ 箱子的球的顏色種類比 $b$ 箱子少，直接把 $a$ 箱子所有的球都丟到 $b$ 箱子，再把 $a$ 箱子的球清空。 複雜度？ ---- 最差情況是每次操作時 $a$.size() $=$ $b$.size() 可以畫成下方的樹  ---- 因此考慮選擇小的箱子合併到大的箱子，做完 $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)$ --- 寫[題單](https://vjudge.net/contest/716076)！