<style> .reveal .slides { text-align: left; font-size:30px } </style> # Advanced Tree Algorithm ---- - Heavy Light Decomposition - DSU on Tree - Tree Hash --- ## 樹鏈剖分 ### Heavy Light Decomposition ----  顧名思義，把樹剖分成很多條鏈 ----  對於每一條鏈轉換成序列上連續的位置，用資料結構去維護(如線段樹、樹狀數組之類)  ----  有兩種剖分的方法：長鏈剖分、輕重鏈剖分 由於長鏈剖分比較冷門，所以這邊只介紹輕重鏈剖分 通常樹鏈剖分會直接代表輕重鏈剖分 ---- ### 能解決的問題 用來處理樹上路徑詢問、修改等問題。 e.g. 給一棵大小為 $n$ $(1\le n\le 2\cdot 10^5)$ 的樹， $q$ $(1\le q\le 2\cdot 10^5)$ 筆操作， 每次為以下兩種其中一種： - 詢問從點 $a$ 到點 $b$ 的路徑上路徑總和 - 點 $a$ 到點 $b$ 的路徑上經過的點加值 $v$ ---- ### 作法 --- 路徑拆解 把路徑拆成多條樹上的鏈，對於每條鏈用資料結構維護、詢問  以詢問路徑 6-10 為例，等價於拆成 6-6, 4-1, 9-10 三條鏈的路徑分別去詢問 ---- ### 另一個例子  以加值路徑 7-5 的所有點權重加值 10 為例，等價於拆成 7-2, 5-5 兩條鏈分別去對於區間加值 10 ---- 把路徑拆成很多條鏈，對於每條鏈花 $O(\log n)$ 詢問/修改 因此每次詢問/修改的複雜度為 $O(走過的鏈數量\times \log n)$ 那總共會經過幾條呢 ? ---- 在證明之前先介紹一些會用到的名詞們 ---- ### 名詞介紹 **重兒子**：每個點的子樹中，子樹大小(即節點數)最大的子節點 **輕兒子**：除重兒子外的其他子節點 **重邊**：每個節點與其重兒子間的邊 **輕邊**：每個節點與其輕兒子間的邊 **重鏈**：重邊連成的鏈 **輕鏈**：輕邊連成的鏈 <div style=" position: absolute; top: 150px; right: -50px; width: 450px; height: 300px;">  </div> ---- ### 證明 --- 每次操作最多只會經過 $\log n$ 條鏈 往重兒子走不會換鏈 而往輕兒子走則會換一條鏈，因此經過的鏈數量則為往輕兒子走的數量  以上圖為例， 1-12 的路徑經過兩次輕兒子，會換兩次鏈 ---- ### 從根節點出發最多只會換 $\log n$ 條鏈 由於我們使用輕重鏈剖分， 輕兒子的子樹節點數量必定 < $\frac{1}{2}$ 當前節點子樹大小 複雜度最差為一直往輕兒子走，但每次都會減少至少 $\frac{1}{2}$ 的節點數量 所以從根節點走下來最多只會換 $\log n$ 條鏈  而完美二元樹的形狀每次分剛好一半，會使得最差情況換鏈次數最多 ---- ### 證明 --- 每次操作最多只會經過 $\log n$ 條鏈 而一條路徑 $u$ 到 $v$ ，我們可以把它拆成兩段 $u$ 到 $\texttt{lca}$ 以及 $\texttt{lca}$ 到 $v$ 而根據上一頁，從任意節點往下走最多只會換 $\log n$ 條鏈， 因此從 $\texttt{lca}$ 到 $u$ 以及 $\texttt{lca}$ 到 $v$ 也分別只需要換最多 $\log n$ 條鏈 ---- ### 操作複雜度 每筆操作經過最多 $O(\log n)$ 條鏈， 每條鏈搭配資料結構只需要 $O(\log n)$ 詢問/修改 所以每次詢問/修改的操作複雜度為 $O(\log^2 n)$ 總共 $q$ 筆操作，總複雜度為 $O(q\log^2 n)$ ---- ### 樹鏈剖分實作 分成兩次 DFS 通常以 1-base 實作，一開始把所有節點重兒子設為 0 (0 當成沒有子節點) ---- ### 第一次 DFS --- 找重兒子 需要紀錄當前節點的子樹大小(sz)、深度(dep)、重兒子(son)、父節點(fa) ```cpp [|3,4,5,6,7|4,5,6,8|] int sz[MXN], dep[MXN], son[MXN], fa[MXN]; void dfs_sz(int x, int f, int d){ //當前節點 x ，父節點 f，深度 d sz[x] = 1; dep[x] = d; fa[x] = f; for(int i : edge[x]){ if(i == f) continue; dfs_sz(i, x, d+1); sz[x] += sz[i]; if(sz[son[x]] < sz[i]) son[x] = i; } } ``` 重兒子一開始設為 0， 重兒子存法為找出所有子節點中子樹大小最大的 沒有子節點的話 son[x] 為 0 ---- ### 第二次 DFS --- 樹鏈剖分 把每個節點根據鏈的走訪順序編號(dfn) 此編號為在線段樹上的位置 並記錄每個節點所在的鏈的頂端節點(top) ```cpp= int top[MXN]; // 維護每個節點所在的鏈的頂端節點 int dfn[MXN], rnk[MXN]; int cnt = 0; void dfs_hld(int x, int f){ top[x] = (son[fa[x]] == x ? top[fa[x]] : x); rnk[cnt] = x; // 紀錄每個編號為哪個節點 dfn[x] = cnt++; // 走到當前節點時編號 if(son[x]) dfs_hld(son[x], x); // 優先遍歷重兒子，使得編號連續 for(int i : edge[x]){ if(i == f || i == son[x]) continue; dfs_hld(i, x); } } ``` ---- ### 求出 lca 不斷跳鏈，直到 $u$ 和 $v$ 跳到同一條鏈上為止。 每次跳鏈選所在的鏈頂端深度較深的一端往上跳。  以 6-12 為例， 6-6 $\to$ 12-12 $\to$ 9-10 $\to$ 1-4 ---- ### 求出 lca --- 範例程式碼 ```cpp= int getLca(int u, int v) { while(top[u] != top[v]){ if(dep[top[u]] > dep[top[v]]) u = fa[top[u]]; else v = fa[top[v]]; } return dep[u] > dep[v] ? v : u; } ``` ---- ### 路徑修改/詢問 $u$ 到 $v$ 路徑上操作可以拆成 $u$ 到 $\texttt{lca}$ 、 $v$ 到 $\texttt{lca}$ 兩條路徑 即可使用剛剛的作法在跳鏈時不斷更新/詢問 ---- 求路徑上權重總和 ```cpp= int query(int u, int v) { int ret = 0; while(top[u] != top[v]){ if (dep[top[u]] > dep[top[v]]){ ret += segtree.query(dfn[top[u]], dfn[u]); u = fa[top[u]]; } else{ ret += segtree.query(dfn[top[v]], dfn[v]); v = fa[top[v]]; } } // 最後到同一條鏈上 ret += segtree.query(min(dfn[u], dfn[v]), max(dfn[u], dfn[v])); return ret; } ``` ---- ### 使用樹鏈剖分對子樹操作 如果題目的操作多了子樹詢問? 1. 詢問路徑 $u$ 到 $v$ 的路徑點權總和 2. 路徑 $u$ 到 $v$ 的點加值 $k$ 3. **詢問子樹 $u$ 的點權總和** 4. **子樹 $u$ 的所有點的點權加值 $k$** ---- 而我們維護的編號順序，子樹的編號會是連續的， 因此題目需要求子樹時，我們可以多紀錄子樹中最大的 dfn 編號(bottom) ```cpp= int bottom[MXN]; // 維護每個節點的子樹中最大 dfn 編號 int dfs_hld(int x, int f){ top[x] = (son[fa[x]] == x ? top[fa[x]] : x); rnk[cnt] = x; bottom[x] = dfn[x] = cnt++; if(son[x]) bottom[x] = max(bottom[x], dfs_hld(son[x], x)); // 更新子樹最大編號 for(int i : edge[x]){ if(i == f || i == son[x]) continue; bottom[x] = max(bottom[x], dfs_hld(i, x)); // 更新子樹最大編號 } } ``` ---- 樹鏈剖分是強大的東西，但沒有必要時請不要亂用 :poop: 除非是動態更新/詢問的題目才會用到， 沒有動態更新的路徑問題使用一般的 LCA 或者樹上差分 都可以通過 --- ## 啟發式合併 ### Disjoint Set Union-find on tree, Small to Large 一種非常暴力的算法，通常用於子樹上統計問題 使用小合併到大的順序統計會使得看似很差的複雜度變成好的 ---- ### DSU on Tree? 並查集有路徑壓縮下 單筆操作複雜度為 $O(alpha(n))$ 趨近於常數 而有些情況並查集不能路徑壓縮(需要持久化時)，使得單筆操作最差複雜度提升到 $O(N)$ 路徑壓縮 ```cpp= int find(int x){ if(f[x] == x) return x; return f[x] = find(f[x]); } ``` 少了路徑壓縮 ```cpp= int find(int x){ if(f[x] == x) return x; return find(f[x]); } ``` ---- 為了解決這個問題，在並查集中合併時， 會判斷子樹大小來選擇誰合併到誰 ```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 當成自己的 好像就可以減少一些時間。 ---- 以下用指標實作 ```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); mp[x] = mp[son[x]]; ans[x] = ans[son[x]]; } else{ mp[x] = new map<int,int>(); ans[x] = 1; } (*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)$ --- ## Tree Hash 根據樹的形狀把整棵樹 Hash 成一個值。 進而可以 `O(1)` 判斷兩棵樹是否為同構 ---- ## isomorphism 同構圖的定義為給定兩張圖其節點數量相同，且在兩張圖重新編號後能夠使得任兩個點對其連邊狀況相同   上兩張圖為同構圖，把左邊那張編號為 3, 4 的節點交換編號後，其任一點對連邊狀況相同 ---- ## Rooted Tree Hash 給定兩棵有根樹，判斷是否為同構的有根樹   以上為同構有根樹，每個節點的子節點可以重新排列順序後相同 ---- ## 作法 rolling hash on tree hash(u) = $\sum$ hash$(v)\times p^i$ % mod 1. 算出每個子樹 $v$ 的 hash 值 2. 把所有子樹 $v$ 的 hash 值排序 3. 依序把每個子樹 $v$ 的 hash 值加入計算 *葉節點的 hash 值為 1 ---- 1. 算出每個子樹的 hash 值 2. 把所有子樹的 hash 值排序 3. 依序把每個子樹的 hash 值加入計算 ```cpp [|2-5|6|7-10|] ll dfs(int u){ vector<ll> h; subtree_sz[u] = 1; for(ll child : edge[u]){ h.push_back(dfs(child)); subtree_sz[u] += subtree_sz[child]; } sort(h.begin(), h.end()); ll ret = subtree_sz[u]; for(ll v : h){ ret = (ret * base + v) % MOD; } return ret; } ``` ~~如果過不了就多拿幾個參數 hash~~ ~~例如加v時順便加或乘上子樹大小~~ ---- ## 複雜度 每個節點只遍歷一次，每次只排序自己的子節點 hash 值 $O(N\log N)$ ---- ### 2020 ICPC Taipei region --- Problem G. Graph Cards 判斷有幾種不同構的水母圖 (簡單環 + 環上點連出去樹 )  - $\sum n\le 10^6$ ---- ## 作法 先找環 相信大家都會做 ? ---- ## 作法 把環上連出去的樹分別去做 hash 把所有環上的每棵樹縮點成整棵樹的 hash 值  題目轉換等價於求 幾種不同構的環狀序列 ---- 幾種不同構的環狀序列 ? [minimum rotation](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/minRotation.cpp) ! 轉一下序列，把序列變成最小字典序為開頭 即可比較兩個環狀序列是否相同 模板 minimum rotation 可以 $O(N)$ 做到求出最小字典序旋轉 函數會回傳要把哪個位置當成開頭 內建函數 rotate() 可以幫你旋轉不用自己轉 ---- ## 無根樹判斷同構? 由於一棵樹的重心最多只有兩個，因此我們可以直接用重心當根 去做有根樹 hash 判斷兩棵樹是否為同構只需要判斷兩個重心的 hash 值是否相同即可 --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/567266) 暑假的課沒有比較輕鬆，請各位務必跟上練習， 否則開學後的課程會跟不上