<style> .reveal .slides { text-align: left; font-size:30px } </style> # Advanced Tree Algorithm ---- - Tree Hash - Heavy Light Decomposition - Virtual Tree --- ## Tree hash 樹去做 hash ，把樹的形狀 hash 成一個值 O($\log n$) 判斷是否同構 ---- ## isomorphism 同構 同構圖的定義為給定兩張圖其節點數量相同，且在兩張圖重新編號後能夠使得任兩個點對其連邊狀況相同   上兩張圖為同構圖，把左邊那張編號為 3, 4 的節點交換編號後，其任一點對連邊狀況相同 ---- ## Rooted Tree Hash 給定兩棵有根樹，判斷是否為同構的有根樹   以上為同構有根樹，每個節點的子節點可以重新排列順序後相同 ---- ## 作法 ### 直接交給map判斷是否同構 給每種有根樹一個 unique id 把每個兒子的 id 丟進vector 後排序 再把vector 存進 map 維護 ```cpp map<vector<int>, int> id; int dfs(int x, int f){ vector<int> sub; for (int v : edge[x]){ if (v != f) sub.push_back(dfs(v, x)); } sort(sub.begin(), sub.end()); if (!id.count(sub)) id[sub] = id.size(); return id[sub]; } ``` ---- ## 複雜度 每個節點只遍歷一次，每次只排序自己的子節點 id 值，並且存進 map 中 $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 值是否相同即可 --- ## Heavy Light Decomposition 輕重鏈剖分 ---- 顧名思義 把樹分成很多條重鏈和輕鏈  ---- 每條鏈對應到一個連續的序列，接著去做動態序列問題，用線段樹等資料結構維護  ---- ## 能用樹鏈剖分解決的問題 用來處理樹上路徑詢問、修改等問題 例如： 給一棵大小為 $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-10 的所有點權重加值 10 為例，等價於拆成 7-1, 9-10 兩條鏈分別去區間加值 10 ---- 每次詢問和修改是對所有經過的鏈去做 $O(\log n)$ 的操作 因此一次操作複雜度為 $O(經過的鏈數量 \cdot \log n)$ 讓我們來證明經過的鏈數量最多會是多少吧~~ ---- ### 在證明之前先介紹樹鏈剖分所需名詞們 <hr> **重兒子**：每個點的子樹中，子樹大小(即節點數)最大的子節點 **輕兒子**：除重兒子外的其他子節點 **重邊**：每個節點與其重兒子間的邊 **輕邊**：每個節點與其輕兒子間的邊 **重鏈**：重邊連成的鏈 **輕鏈**：輕邊連成的鏈 <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)$ ---- ## 樹鏈剖分實作 通常用 1-base 實作，0 代表空的子節點 分成兩遍 DFS ---- 第一次 DFS 求：「父節點(par)」、「深度(dep)」、「子樹大小(sz)」、「重兒子(son)」 ```cpp int par[MXN], dep[MXN], sz[MXN], son[MXN]; void dfs1(int now, int fa, int now_deep){//當前節點, 爸爸, 目前深度 dep[now] = now_deep; par[now] = fa; sz[now] = 1; for(auto nxt : v[now]){ if(nxt == fa)continue; dfs1(nxt, now, now_deep + 1); sz[now] += sz[nxt]; if(sz[nxt] > sz[son[now]]) son[now] = nxt; } } ``` 一開始要先 `memset(son,0,sizeof(son));` 並讓 `sz[0]=0` 代表 0 這個點的 sz 為 0 跑完第一次 dfs 之後，son 為 0 的點代表沒有子節點 ---- 第二次 DFS 求：「走訪編號(dfn)」、「目前點所在的鏈的頂端點(top)」 dfn 為走訪編號，此編號為線段樹上的位置 ```cpp int top[MXN], dfn[MXN], rnk[MXN]; int cnt = 0; void dfs2(int now, int fa, int now_top){//現在的點, 爸爸, 目前的頂端點 top[now] = now_top; rnk[now] = cnt; dfn[now] = cnt++; if(son[now] != 0) dfs2(son[now], now, now_top);//為了讓編號連續，先往重兒子走 for(auto nxt : v[now]){ if(nxt == fa || nxt == son[now])continue; dfs2(nxt, now, nxt);//往其他輕兒子走 } } ``` 這樣鏈就建好了，樹上的點權就根據 dfn 丟進資料結構去維護 ---- ## 求出兩點的 LCA 不斷往上跳鏈，直到跳到同一條鏈為止 跳到同一條鏈之後檢查哪一個深度較低，深度低的為LCA  以 6和12 為例 6 : 6 $\to$ 4 12 : 12 $\to$ 10 $\to$ 1 4 和 1 在同一條鏈上，1 為深度低的，也就是 6 和 12 的 LCA ---- ## LCA -- 範例 code ```cpp int getlca(int x,int y){ while(top[x] != top[y]){ if( dep[top[x]] < dep[top[y]] )//根據頂端點的深度往上跳 y = par[top[y]]; else x = par[top[x]]; } if(dep[x] > dep[y])return y;//這時候在同一條鏈了，回傳比較不深的點 else return x; } ``` ---- ## 樹上路徑修改or 詢問 可以用剛才跳鏈的方式 $O(\log^2 n)$做到 對於 $x$ 到 $y$ 的路徑可以分成 $x \rightarrow lca$ 和 $y \rightarrow lca$ 分別去跳鏈 ---- 求路徑上點權重總和 ```cpp int query(int x, int y){ int lca = getlca(x, y); int ans = 0; //x -> lca 點權總和 while( top[lca] != top[x] ){ ans += seg.query( dfn[top[x]], dfn[x] ); x = par[top[x]]; } ans += seg.query( dfn[lca], dfn[x] ); //y -> lca 點權總和 while( top[lca] != top[y] ){ ans += seg.query( dfn[top[y]], dfn[y] ); y = par[top[y]]; } ans += seg.query( dfn[lca], dfn[y] ); ans -= seg.query( dfn[lca], dfn[lca] );//lca被重複算到一次，要扣掉 } ``` ---- ## 利用樹剖，對子樹做操作 如果題目的操作多了子樹詢問? 1. 詢問路徑 $u$ 到 $v$ 的路徑點權總和 2. 路徑 $u$ 到 $v$ 的點加值 $k$ 3. **詢問子樹 $u$ 的點權總和** 4. **子樹 $u$ 的所有點的點權加值 $k$** ---- 對子樹操作大家應該都會直覺用樹壓平，利用「進入點的時間」和「離開點的時間」進行區間加值或查詢。 在樹鏈剖分中，進入點的時間為 dfn ，再多一個陣列紀錄離開點的時間就好了 ---- ```cpp int top[MXN], dfn[MXN], rnk[MXN]; int out[MXN];//離開點的時間 int cnt = 0; void dfs2(int now, int fa, int now_top){ top[now] = now_top; rnk[now] = cnt; dfn[now] = cnt++; if(son[now] != 0) dfs2(son[now], now, now_top); for(auto nxt : v[now]){ if(nxt == fa || nxt == son[now])continue; dfs2(nxt, now, nxt); } out[now] = cnt - 1;//因為 dfn 有 ++，所以要減 1 } ``` 接著就跟樹壓平一樣 用 dfn 和 out 去做詢問 or 修改就行了 ---- 樹鏈剖分是強大的東西，但沒有必要時請不要亂用!!! 除非是動態更新/詢問的題目才會用到， 沒有動態更新的路徑問題使用一般的 LCA 或者樹上差分 都可以通過 --- ## Virtual Tree ---- ## 引入例題 : 給你一棵大小為 $n$ 、 以 $1$ 為根的樹，再給 $q$ 筆詢問，每筆詢問給定 $k$ 個點的點集$\{a_1,a_2,a_3...a_k\}$，問點 $1$ 走到這些點的路徑聯集邊數數量。 $n \leq 2 \cdot 10^5$ , $1 \leq q \leq 10^6$ , $1 \leq \sum k \leq 10^6$ ---- $q$ 筆詢問，每筆詢問給一個點集  假設選擇點集 $\{3,4,5\}$ , 路徑聯集起來的邊數數量為 $4$ ---- 先想一下 $q=1$ 的情況.... - 可以發現 $q=1$ ，代表只有一個詢問 - 只要把給定的點集標起來，跑一遍 DFS 做樹 DP 往上轉移 - 複雜度 $O(n)$ ---- 但是這題目最多有 $10^6$ 個詢問，顯然沒有辦法對每筆詢問做一次樹 DP 這樣做時間複雜度為 $O(nq)$ ，得到TLE >:( ---- 可以觀察到對於每筆詢問，有些點是不重要的  選取$\{8,9\}$，就只有$\{1,2,4,8,9\}$需要處理 而虛樹就是把不重要的點忽略掉，把重要的點拉出來做樹上問題 ---- ## Virtual Tree 虛樹 定義要選取的點稱為「關鍵點」、點集 $S$ 為關鍵點們兩兩一組的 LCA 們 而 $S$ 和關鍵點們就會是虛樹的點!  $\{3,5,9,11\}$為關鍵點們，$S=\{1,2,3\}$為 LCA 們 因此虛樹包含這些點 : $\{1,2,3,5,9,11\}$ ##### 後面會說明為什麼需要LCA們 ---- 定義點集 $S$ 為關鍵點們兩兩一組的 LCA 們，假設關鍵點有 $k$ 個，求出 $S$，暴力做下去會是 $O(k^2 \cdot \log (n))$ ，很差 所以要用聰明的方式得出這些 LCA 們 ---- 考慮用 dfn(dfs序) 對關鍵點去做排序 ，再相鄰兩兩求出 LCA 原本關鍵點們 : $\{3,5,9,11\}$ dfn 排序之後 : $\{3,11,9,5\}$ 接著兩兩去做LCA求出點集 $S$ - LCA(3,11)=3 - LCA(11,9)=2 - LCA(9,5)=1 <div style="position: absolute; left: 60%; top:10%;">  </div> ---- 所以虛樹的點為 關鍵點 $+$ $S=\{3,5,9,11\}+\{1,2,3\}$  一次詢問總複雜度 : $O( k \log n )$ ---- 對於一次詢問，虛樹的大小為關鍵點數量+LCA數量 關鍵點有 $k$ 個，LCA數量最多有 $k-1$ 個 因此虛樹大小最大為 $2k-1$個  虛樹大小為$2k-1$的情況如上>< ---- 回到問題，求點 $1$ 走到這些點的路徑聯集邊數數量。 跟虛樹有甚麼關係呢? ----  可以發現虛樹把一些邊和點都省略掉了，只要處理虛樹的所有邊就行 ---- 對於虛樹的所有邊，可以都可以對應到原樹的路徑  假設在虛樹中存在一條 u 連 v 的邊，相當於對原樹 u -> v 路徑去做路徑問題，在這題是要求出 u 到 v 的路徑長度 虛樹中最多有 $2k-1$ 個點，有 $2k-2$ 個邊，會做 $2k-2$ 次路徑詢問 ---- 求出每條 u->v 的路徑長度 - 3->11 : 長度為2 - 2->3 : 長度為1 - 2->9 : 長度為2 - 1->2 : 長度為1 - 1->5 : 長度為1 答案為 2+1+2+1+1=7 <div style="position: absolute; left: 40%; top:10%;">  </div> ---- ## 題外話:為甚麼虛樹需要 LCA 們 而「關鍵點+LCA們」所建立的虛樹上，每個邊可以被很好的當成原樹的路徑詢問 這就是為甚麼我們需要LCA這些點  只有關鍵點的話，會不知道要做哪些路徑詢問 ---- 每筆詢問有 $2k-2$ 條邊要解決 $\rightarrow O(k)$ 求出路徑長度這件事情可以用倍增法解決 $\rightarrow O(\log n)$ 而 $q$ 筆詢問的 $k$ 總共有 $\sum k$，因此總複雜度 $\rightarrow O(\sum k \cdot \log n)$ ---- 那這裡有一個小細節 其實不用建出真正的虛樹再去做路徑詢問，可以利用原樹上對應的點dfn來判斷要如何求需要查詢的路徑們 ---- 步驟: 1. 把在虛樹上的點也按照 dfn 排序 2. 對排序好的數列從左到右把相鄰兩個數字$\{a,b\}$抓出來 3. 對於每個$\{a,b\}$，對原樹上做 LCA($a$,$b$) -> b的路徑詢問 ---- 虛樹根據 dfn 排序之後為$\{1,2,3,11,9,5\}$，接著會做以下路徑詢問: - LCA(1,2) ->2 - LCA(2,3) ->3 - LCA(3,11)->2 - LCA(11,9)->3 - LCA(9,5) ->2 <div style="position: absolute; left: 40%; top:10%;">  </div> &nbsp; &nbsp; 這樣就可以省略掉建樹的過程， 直接用 dfn 決定要用哪些路徑需要詢問 ---- 得出虛樹的點 be like : ```cpp vector<int>virTree(vector<int> ver) { sort(ver.begin(),ver.end(),cmp); //用dfn排序 vector<int>res(ver.begin(),ver.end()); for(int i=1;i<ver.size();i++){ res.push_back(lca(ver[i-1],ver[i]));//把LCA丟進虛樹內 } sort(res.begin(),res.end(),cmp);//在用dfn排序 res.erase(unique(res.begin(),res.end()), res.end());//可能會有重複的點，需要去掉重複的 return res; } ``` ---- 解決樹上路徑問題 be like: ```cpp int count_answer(vector<int>virTree){ sort(virTree.begin(),virTree.end(),cmp); int ans=0; for(int i=1;i<virTree.size();i++){ ans+=query(lca(virTree[i-1],virTree[i]),virTree[i]); } return ans; } ``` ---- 虛樹的題目都是大同小異，就只差在每個路徑需要詢問的事情是甚麼。 如果你看到題目有很多筆詢問，每筆詢問要選一些點做樹上問題，關鍵點數量總和不超過某個上限，那大概率就會是虛樹的題目 :D