<style> .reveal .slides { text-align: left; } </style> # Advanced Tree Algorithm Competitive programming 2 2021/11/01 ---- * 樹DP (DP on Tree) * 啟發式合併 (DSU on Tree) * 樹鏈剖分 (Heavy-Light Decomposition) * ~~樹重心 (Tree Centroid)~~ --- ## 樹DP ### (DP on tree) * 遞迴求解 * 通常使複雜度降低一個維度 $O(N^2) \to O(N)$ $O(N^3) \to O(N^2)$ * dp[i] 通常代表以第i個點為根的子樹最佳答案 ---- ### 直接來看例題 <div style="font-size: 30px"> 給你一棵有 $N$ 個點的樹，求樹上全點對距離總和 即求 $\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} length(i,j)$  以上圖為例總合為 (1+1+1+2)+(1+2+2+3)+(1+2+2+1)+(1+2+2+3)+(2+3+1+3) = 36 </div> ---- ### 暴力一點 * $O(N^3)$ 窮舉每個點對，DFS暴力兩點的距離 * $O(N^2)$ 每個點當起點DFS，走到每個點把總和記下來 ---- ### $O(N)$ 樹DP DFS 兩次 第一次 <div style="font-size: 30px"> 找一個點 (這邊以節點1為根) 當根， 算出所有點的子樹到自己的距離總和 </div> 第二次 <div style="font-size: 30px"> 遞迴到每個點順便算每個點到當前點的距離 </div> ---- ### 第一次DFS <div style="font-size: 30px"> 算每個節點的子樹到自己的距離總和，以及子樹大小 dp[i] 的定義為以節點i為根的子樹到節點i的距離總和 </div>  <div style="font-size: 30px"> dp[1] = dp[2] + dp[3] + dp[4] + (sz[1]-1) = 5 dp[2] = 0 dp[3] = dp[5] + (sz[3]-1) = 1 dp[4] = 0 dp[5] = 0 </div> ---- ### sample code ```cpp= pair<int,ll> dfs1(int x,int f){ sz[x] = 1; dp[x] = 0; for(int i:edge[x]){ if(i == f) continue; pair<int,ll> value = dfs1(i,x); sz[x] += value.first; dp[x] += value.second; } return make_pair(sz[x], dp[x]+sz[x]); }//return value : subtree size, subtree distance sum ``` ---- ### 第二次DFS <div style="font-size: 30px"> 從根節點開始算每個節點到自己的距離總和 根節點1到每個節點的距離總和就是 dp[1] </div>  ---- ### 遞迴下去其他節點 <div style="font-size: 23px"> 從根結點遞迴下去到節點3，這時我們會傳一個參數下去 從父節點方向來的節點到當前節點距離總和 也就是 (dp[1]-(dp[3]+sz[3])) + dp[3] + (sz[1]-sz[3]) ( 父節點方向到節點3的距離總和 + 自己子樹到節點3距離總和 + 父節點方向的節點數量 ) </div>  ---- ### sample code ```cpp= void dfs2(int x,int f,ll sum){ ans += sum + dp[x]; //所有點到結點x距離總和為父節點方向距離總和 + 子樹到自己距離總和 for(int i:edge[x]){ if(i == f) continue; //tmp 為從父節點x到子節點i的距離總合為 ll tmp = sum //x的父節點總和 sum 到結點x的距離 + dp[x] - (dp[i]+sz[i]) //加上x的子樹(除了i方向)到x的距離總和 + n - sz[i]; //加上從節點x到節點i的距離 dfs2(i, x, tmp); } } ``` ---- ### main function 總複雜度 $O(N)$ ```cpp= int main(){ build_tree(); // O(N) dfs1(1,1); // O(N) dfs2(1,1,0); // O(N) cout<<ans<<endl; } ``` --- ## 啟發式合併 ### (Disjoint Set Union-find on tree) <div style="font-size: 30px"> 並查集一般寫法下 單筆操作複雜度為 $O(alpha(n))$ 趨近於常數 而持久化並查集不能路徑壓縮，使得單筆操作複雜度提升到 $O(N)$ 因此要使用啟發式合併來降低複雜度，單筆操作複雜度為 $O(lgN)$ </div> ---- ### find 函式 路徑壓縮 ```cpp= int find(int x){ if(f[x] == x) return x; return f[x] = find(f[x]); } ``` 少了路徑壓縮 最差複雜度為 $O(N)$ ```cpp= int find(int x){ if(f[x] == x) return x; return find(f[x]); } ``` ---- ### 啟發式合併 <div style="font-size: 30px"> 每次合併時，把小的往大的合併 先來看以下兩種極端例子 </div> ---- ### (1) <div style="font-size: 30px"> 其中一邊的樹比另一邊大很多， 當小的合併到大的時候複雜度趨近於常數 </div> <div style="position: absolute; right: 70%; top:100%;">  </div> <div style="position: absolute; right: 10%; top:100%;">  </div> ---- ### (2) <div style="font-size: 30px"> 當兩邊大小差不多時， 合併的複雜度為 $O(n)$ (n為樹的大小) </div> <div style="position: absolute; right: 70%; top:100%;">  </div> <div style="position: absolute; right: 10%; top:100%;">  </div> ---- <div style="font-size: 30px"> 因此可以發現兩種情況中，如果每次合併都是第一種 把小的合併到大的，那[均攤複雜度](https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%91%8A%E5%88%86%E6%9E%90)為 $O(N)$ 但如果每次都是第二種，複雜度會變多少? </div> ---- 答案是 $O(NlgN)$  ---- <div style="font-size: 30px"> 因此透過每次小的合併到大的 最差複雜度為 $O(NlgN)$ </div> ```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; } ``` ---- #### 用途 <div style="font-size: 30px"> 當需要用到子樹的資訊，每次去合併時 如果每次都把小的合併到大的，最差複雜度 $O(NlgN)$ </div> #### 例題 給一棵大小為n(n<=1e5) 的有根樹 每個節點上都有塗上一種顏色 問以 1~n 為根的子樹中，出現最多次的顏色數量為何？ ---- <div style="font-size: 35px"> 用一個map紀錄不同顏色的數量 最差情況：每個節點顏色都不同 照子樹大小去合併，複雜度為 $O(NlgNlgN)$ 啟發式合併 $O(NlgN)$ * map複雜度 $O(lgN)$ </div> ---- <div style="font-size: 35px"> 記得正常情況下的並查集，只需使用路徑壓縮即可 除非是需要用到 啟發式合併的技巧 或者 持久化並查集 再用啟發式合併 </div> --- ## 樹鏈剖分 ### (Heavy Light Decomposition) <div style="font-size:25px"> 有兩種剖分的方法：長鏈剖分、輕重鏈剖分 由於長鏈剖分不太會出現，所以這邊只介紹輕重鏈剖分 顧名思義，將樹分成很多條鏈， 對每一條鏈用資料結構去維護(如線段樹、樹狀數組之類) 樹上路徑詢問、修改 EX：樹上從點$a$到點$b$的路徑上，詢問總和 or 經過的點加值 </div> ---- ### 名詞介紹 <div style="font-size:25px;"> **重兒子**：每個點的子樹中，子樹大小(即節點數)最大的子節點 **輕兒子**：除重兒子外的其他子節點 **重邊**：每個節點與其重兒子間的邊 **輕邊**：每個節點與其輕兒子間的邊 **重鏈**：重邊連成的鏈 **輕鏈**：輕邊連成的鏈 </div> <div style=" position: absolute; top: 150px; right: -50px; width: 600px; height: 300px;">  </div> ---- <div style="background-color:white">  </div> ---- 作法 - 兩次DFS: 1. 找重兒子 2. 樹鏈剖分 3. 對每條鏈建資料結構 ---- ### 找重兒子 <div style="margin-left:-180px"> ```cpp= //假設1-base，並且0為指向空節點,sz[0]=0 void dfs1(int x,int f,int d){ depth[x]=d; //紀錄深度 father[x]=f; //設父節點 sz[x]=1; //將自己本身加進子樹大小 son[x]=0; //一開始先指向空 for(int i=0;i<edge[x].size();i++){ if(edge[x][i]==f) continue; dfs1(edge[x][i],x,d+1); //dfs下去紀錄每個子樹的大小 sz[x]+=sz[edge[x][i]]; //將子樹大小加至自己 if(sz[edge[x][i]]>sz[son[x]]) son[x]=edge[x][i]; //找重兒子 } } ``` </div> ---- ### 樹鏈剖分 <div style="margin-left:-180px"> ```cpp= int treeSz=1; void dfs2(int x,int f){ for(int i=0;i<edge[x].size();i++){ if(edge[x][i]==f) continue; if(edge[x][i]==son[x]) //判斷是否為重兒子 root[edge[x][i]]=root[x]; //若為重兒子則將連至上面的鏈 else root[edge[x][i]]=edge[x][i],treeSz++; //否則剖分成新鏈 dfs2(edge[x][i],x); } len[root[x]]++; //更新每條鏈的長度 } ``` </div> ---- ### 對每條鏈建資料結構 <div style="margin-left:-180px"> ```cpp= vector<int> treeID; vector<vector<int>> tree; void buildEachTree(){ tree.resize(treeSz); for(int i=1,j=0;i<=n;i++){ if(root[i]==i){ //判斷鏈的開頭 treeID[i]=j++; //設為第j條鏈 tree[treeID[i]].resize(len[i]*4,0); //以線段樹為例 } //設第j條鏈的長度4倍大小 } } ``` </div> ---- ### 樹鏈剖分完以後， ### 如何路經修改、詢問? ---- <div style="margin-left:-180px"> ```cpp= void updatePath(int x,int y,int v){ while(root[x]!=root[y]){ //若不在同一條鏈上 if(depth[root[x]]>depth[root[y]]){ //優先更新深度深的鏈 update(treeID[root[x]],0,dep[x]-dep[root[x]],v); x=father[root[x]]; } else{ update(treeID[root[y]],0,dep[y]-dep[root[y]],v); y=father[root[y]]; } } int mn=min(dep[x],dep[y]),mx=max(dep[x],dep[y]); //更新第treeID[i]樹從mn~mx的範圍加值v update(treeID[root[x]],mn,mx,v); //最後會連至同一條鏈上，更新範圍 } ``` </div> ---- ### 複雜度分析 <div style="font-size:30px;"> 由於剖分的性質，會使任一個點至根結點最多經過$lgN$條鏈， 每條鏈上的詢問、修改為$O(lgN)$ 因此每筆詢問、修改為$O(lgNlgN)$ Q筆詢問則複雜度為$O(QlgNlgN)$ </div> ---- 用樹鏈剖分找最近共同祖先 ```cpp= void getLca(int x,int y){ while(root[x]!=root[y]){ if(depth[root[x]]>depth[root[y]]) x=father[root[x]]; else y=father[root[y]]; } return depth[x]>depth[y]?y:x; } ``` <div style="font-size:25px"> 最多經過 $lgN$ 條鏈，因此複雜度為 $O(lgN)$ </div> --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/466109) <div style="font-size: 30px"> 提交期限兩星期，下下星期一 18:30 截止 </div>