<style> .reveal .slides { text-align: left; font-size:33px; } </style> ## Centroid Decomposition & Tree Hash --- ## Centroid Decomposition 重心剖分 (樹分治)，透過每次不斷找到當前子圖的重心，重心拔掉再遞迴下去分割的子樹找各自的重心 重心的定義為一棵樹把節點 $G$ 移除之後，其最大的連通塊會是最小的，而我們會稱節點 $G$ 是樹重心。 ---- ## 如何找到樹重心 先選一個點為根節點，暴力 $O(n)$ 跑過所有節點紀錄每個節點的子樹大小 $s_i$。 假設子樹大小分別為 $s_1, s_2,... s_k$，則父節點方向的子樹大小為 $n - 1 - \sum{s_i}$ 樹重心為 max(n-1-$\sum{s_i}, s_1, s_2...s_k)$ 中最小的節點 ---- ## 重心的性質 - 把重心拔掉之後, 所有子樹的大小會 $\le\frac{n}{2}$ - 一棵樹最多兩個樹重心 ---- ## 重心剖分 1. 找到樹重心 2. 把樹重心從圖上移除 3. 遞迴下去連到的子圖 4. 如果子圖大小 >1 回到步驟 1  ---- 找到<span style = "color:red;">樹重心 </span>  ---- 把樹重心從塗上移除，剩下的子圖分別去找各自的樹重心  ---- 找到子圖各自的<span style = "color:orange;">樹重心 </span>  ---- 把樹重心移除，剩下的子圖分別去找個字的樹重心  ---- 找到各自的<span style = "color:green;">樹重心 </span>  ---- ## 複雜度 每次把圖從重心分割，每個子圖最大為原本的一半 最多遞迴 $\log N$ 層 $T(n)=\sum T(s_i) + O(n)$ 複雜度 $O(N\log{N})$ ---- ## 重心樹 對於當前這層的重心與下一層子圖的重心連接可以構出一顆重心樹 由於重心剖分的性質，樹高度不超過 $\log n$  $\to$  ----  $\to$  ---- ## 引入例題 CF 342 E. Xenia and Tree 給你 $n$ 個節點的樹，一開始每個點都是藍色，會有 $m$ 次操作 - 把某個藍點塗成紅色 - 查詢某個點最近的紅點有多遠。 $n, m\le 10^5$ ---- $n, m\le 10^5$ 如果暴力做，直接用一個陣列紀錄每個節點的顏色 - 把某個藍點塗成紅色 $\to$ O(1) 更新某個節點的顏色 - 查詢某個點最近的紅點 $\to$ BFS 找最近的紅色節點 $O(n)$ 很明顯如果每次都是第二種操作，總複雜度為 $O(nm)\to$ TLE ---- ### 換一種作法 先選一個節點為根 每個節點紀錄到子樹中最近的紅色節點距離，沒有則視為無限大 1. 把某個藍點 $v$ 塗成紅色 - 從當前節點 $v$ 開始往根節點方向更新所有祖先的距離  ---- 2. 查詢某個點 $v$ 最近的紅點 - 從當前節點 $v$ 開始往上走 - 每次判斷到某個祖先 $u$ 的距離 + 祖先 $u$ 到他最近的子樹紅色節點距離取最短的  ---- 1. 把某個藍點 $v$ 塗成紅色 - 從當前節點 $v$ 開始往根節點方向更新所有祖先的距離 2. 查詢某個點 $v$ 最近的紅點 - 從當前節點 $v$ 開始往上走 - 每次判斷到某個祖先 $u$ 的距離 + 祖先 $u$ 到他最近的子樹紅色節點距離取最短的 以上兩種 case 只要到根節點距離很遠複雜度就變 $O(n)$ 一樣最差會變成 $O(nm)$ ---- ### 但如果樹是平衡的 ? 如果樹高最高為 $\log n$ 1. 把某個藍點 $v$ 塗成紅色 - 從當前節點 $v$ 開始往根節點方向更新所有祖先的距離 2. 查詢某個點 $v$ 最近的紅點 - 從當前節點 $v$ 開始往上走 - 每次判斷到某個祖先 $u$ 的距離 + 祖先 $u$ 到他最近的子樹紅色節點距離取最短的 則複雜度變成 $O(m \log n)$ ---- ## 用剛剛的重心樹 ? 會發現重心剖分建出來的重心樹樹高最差為 $\log n$  $\to$  ---- ### 把節點 $v$ 塗成紅色 用 mn 陣列紀錄子樹中最近的紅色節點距離，沒有則視為無限大 對於每一次塗色，從當前節點往祖先方向走到重心樹根節點 更新從塗色節點 $v$ 到當前走訪到的節點 $u$ 距離是否為更近的紅色節點 mn[u] = min(mn[u], dis(u, v)) ---- 以塗色節點 5 為例   會更新節點 5, 4, 1 到紅色的最短 ---- ### 詢問節點 $v$ 到最近紅色節點距離 從當前節點往重心樹根節點方向走 每次問走訪到的節點 $u$ 與詢問節點 $v$ 的距離+走訪到的節點 $u$ 到子樹中最近的紅色節點距離 ans = min(ans, dis(u, v) + mn[u]) ---- 詢問節點 7 到紅色最短   答案會是 ```txt= min( 節點 7 到最近紅色點距離, 節點 1 到最近紅色點距離 + 節點 1 到節點 7 的距離) = min(∞, 2+2) = 4 ``` ---- ### 為甚麼這樣是好的 ? 只更新從當前節點到重心樹根結點路徑上的距離，其他節點呢 ? 可以分成兩種 case : 1. 最近的紅色節點在重心樹的子樹中 2. 最近的紅色節點在往根節點方向 ---- #### 1. 最近的紅色節點 $u$ 在重心樹的子樹中 如果節點 $u$ 在詢問節點 $v$ 的子樹中 則在塗色時已經更新過詢問節點 $v$ 到最近紅色節點的距離 因此答案為 mn[v] = dis(u, v) ---- #### 2. 最近的紅色節點 $u$ 在往根節點方向 則到最近的紅色節點必定會先經過詢問節點 $v$ 的某個祖先 $a$ 因此答案為祖先 $a$ 的子樹中最近的節點 + 自己到祖先 $a$ 的距離 mn[a] + dis(a, v) ---- ### 複雜度 每次會從當前節點走到重心樹的根節點 每次會計算樹上兩點之間的距離更新最近距離 由於樹高不超過 $\log n$ 算樹上兩點之間的距離可以 $O(\log n)$ 找 lca， 再透過深度 dep[u]+dep[v]-2*dep[lca] 得到 因此每次操作的複雜度為 $O(\log^2n)$ 總複雜度為 $O(m\log ^2n)$ ---- ### 細節 注意計算距離是算原本那棵樹上的距離 ---- ### 另外一個例題 CSES. Fixed-Length Paths I 給一棵 $N$ $(1\le N\le 2\cdot 10^5)$ 個節點的無根樹，樹上有幾個點對的距離為 $k$ 也就是有幾個長度為 $k$ 的簡單路徑 ---- ### 考慮分治 選一個點 $v$ 計算所有經過他且長度為 $k$ 的路徑 把點 $v$ 拔掉再分成各自的連通子圖遞迴下去計算長度為 $k$ 的路徑 ----  經過當前點 $v$ 的且長度為 $k$ 的路徑分成兩種 1. 以當前點 $v$ 為起點往外的路徑 2. 經過當前點 $v$ 的且不為起始點的路徑 ---- 1. **以當前點 $v$ 為起點往外的路徑** 第一種我們可以從點 $v$ 開始 DFS 紀錄從點 $v$ 到當前節點的長度，如果長度為 $k$ 則答案 + 1 ```cpp= auto dfs = [&](int x, int f, int d) -> void{ if(d == k) ++ans; for(int i : edge[x]){ if(i == f || vis[i]) continue; dfs(i, x, d+1); } }; for(int i : edge[v]){ dfs(i, v, 1); // 遞迴從 v 連出去的節點 i } ``` ---- 2. **經過當前點的且不為起始點的路徑** 第二種等價於從點 $v$ 開始往兩棵相異子樹方向長度分別為 $a, b$ 且 $a+b = k$ 的路徑 我們可以算往某個子樹長度為 $a$ 的路徑有幾個，乘上往其他子樹路徑長度為 $k-b$ 有幾個。 每個子樹都去計算即為答案 ---- 每次從點 $v$ 開始往不同的子樹去遞迴，計算每個子樹當前走到的距離 $d$ 與前面計算過有幾個距離為 $k-d$ (儲存在 cnt 陣列裡) 算完之後再把當前子樹的距離加進去 cnt 陣列裡 ```cpp= auto dfs = [&](int x, int f, int d, bool add) -> void{ if(d == k){ //case 1 ans++; return; } if(add) ans += cnt[k - d]; else cnt[d]++; for(int i : edge[x]){ if(i == f || vis[i]) continue; dfs(i, x, d+1, add); } }; fill(cnt, cnt+sz, 0); for(int i : edge[v]){ dfs(i, v, 0, 0); // 計算完當前子樹的距離與前面窮舉過的距離加進答案 dfs(i, v, 0, 1); // 把當前子樹的距離存進去 cnt } ``` ---- 每次選一個節點 $v$ 計算經過他且長度為 $k$ 的路徑 再把節點 $v$ 要怎麼選會是最好的 ? 每次選節點 $v$ 計算長度為 $k$ 的路徑複雜度最差為 $O(n)$ 如果選重心? ---- 回想一下重心剖分的複雜度計算 $T(n)=\sum T(s_i) + O(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，反正通常都在亂做~~ ---- ## 複雜度 每個節點只遍歷一次，每次只排序自己的子節點 hash 值 $O(NlgN)$ ---- ### 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/535249) 提交期限到 1/13 23:59 截止 ---- ## 本學期課程結束 ! 相信大家都收穫滿滿 ? <div style="font-size:10px"> <div style="position: absolute; right: 10%;"> - Tree - Lowest Common Ancestor - DP on Tree - DSU on Tree - Heavy-Light Decomposition - Centroid Decomposion - Tree hash - Graph - BFS/DFS - Topological Sort - Shortet Path - DSU & MST - SCC/BCC - 2-SAT - Eulerian Path - LCA - String - Trie - Hash - KMP - Manacher - Palindrome tree - Z value - Suffix array - Geometry - Convex hull construction - Sweep Line - Flow & Matching - Flow Construction </div> - Brute Force Search - Backtracking - Memory Search - Meet In the Middle - Math - Modulo Operation - Modular Multiplicative Inverse - Prime - Dynamic Programming - DP on DAG - Stack / Deque - Bitmask DP - 1D/1D Dynamic Programming - Convex hull optimization - Data Structure - Segment Tree - BIT - Sparse Table - Treap - Persistent Data Structure - PBDS - Square Algorithm - Square Root Decomposition - Mo's Algorithm - Game - SG value </div> ---- 希望大家對於之後演算法設計、程式實作、面試等等都會有幫助 並不是只是一個三學分的課而已 之後在寫程式前都能先好好分析複雜度、想想學過的演算法是否可以用上 祝大家聖誕節快樂 :gift: ---- 期末考 1/6 6:30 大家記得來考 : ) 考試內容：練習賽題目、這幾周上課內容