<style> .reveal .slides { text-align: left; font-size:29px; } </style> # Tree Algorithm Introduction to Competitive Programming 2022/04/20 ---- * 樹DP (DP on Tree) * 啟發式合併 (DSU on Tree) * 樹鏈剖分 (Heavy-Light Decomposition) --- ## 樹DP ### (DP on tree) 為了保持DP順序，樹DP通常以**遞迴求解** $DP[i]$ 通常代表以第 $i$ 個點為根的子樹最佳答案 * 一般樹DP * 換根DP ---- ## 例題 ### 樹上最大獨立集 給你一顆 $N (1 \le N \le 10^5)$ 個點的樹， 求最多能同時選多少點，使得選的點彼此都沒有連邊  ---- ### DP 狀態 DP[$x$][0/1] 以節點 $x$ 為根的子樹的最佳解， 第二個維度為要不要選第 $x$ 個節點(0則不選、1代表要選) 對於節點 $x$ 的子樹，分別推出以下兩種狀態 ($i$ 為節點 $x$ 的兒子) DP[$x$][0] = $\sum$ max(DP[i][0],DP[i][1]) DP[$x$][1] = $1+\sum$ DP[i][0] ---- ### DP[x][0] 狀態為 0 代表，不選節點 $x$ 則子節點可選可不選 DP[x][0] = $\sum$ max(DP[i][0], DP[i][1]) ### DP[x][1] 狀態為 1 代表，選節點 $x$ ，則子節點不能選(子節點狀態為 0) DP[x][1] = $1+\sum$ DP[$i$][0] ---- ## DP 計算順序 DP[x][0] = $\sum$ max(DP[i][0],DP[i][1]) DP[x][1] = $1+\sum$ DP[i][0] 在求 DP[x][0/1] 時，會需要用到子節點的 DP 值 因此會先遞迴到最深計算從葉節點開始算 節點 $i$ 的子節點都計算完 DP 值時，即可計算自己的 DP 值 ---- 實作時邊遞迴邊計算 DP 值 ```cpp= int dp[MXN][2]; void dfs(int x,int f){ dp[x][1] = 1; // 狀態[1] 計算自己數量 +1 for(int i:edge[x]){ if(i == f) continue; dfs(i, x); // 先計算完子節點的答案再算自己的 dp[x][0] += max(dp[i][0], dp[i][1]); dp[x][1] += dp[i][0]; } } ``` ---- ## 複雜度 O(N) N個節點，轉移次數為邊的數量(N-1) ---- ### 換根 DP 通常會有兩次 DFS 第一次 DFS 預處理以每個節點 i 為根的子樹的 DP 值 第二次 DFS 使用計算好的 DP 值開始換根，計算分別每個節點為根的 DP 值 ---- ## 例題 給你一棵有 $N$ 個點的樹，求樹上全點對距離總和 即求 $\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n}$ distance$(i,j)$  以上圖為例總合為 (1+1+1+2)+(2+2+3)+(2+1)+(3) = 18 ---- ### 暴力作法 * $O(N^3)$ 窮舉每個點對，DFS O(N)暴力計算兩點的距離 * $O(N^2lgN)$ 窮舉每個點對，使用 LCA O(lgN)計算兩點距離 * $O(N^2)$ 每個點當起點DFS，走到每個點把總和記下來 ---- ### $O(N)$ 樹DP DFS 兩次 第一次 DFS 選一個點當根， 設 dp[i] 為以第 i 個節點為根的子樹 所有節點到自己的距離總和 第二次 DFS 遞迴到每個點，用剛剛算好的 DP 值 計算以每個點為整顆樹的根節點的答案 ---- ### 第一次 DFS 算每個節點的子樹到自己的距離總和，以及子樹大小 dp[x] 為以節點 x 為根的子樹到節點i的距離總和 sz[x] 為以節點 x 為根的子樹節點數量  <div style="font-size: 23px"> dp[x] = $\sum$ (dp[i]+sz[i]) 也就是 x 的所有子節點i的子樹距離總和 + 子樹的每個節點再多走一步 dp[1] = (dp[2]+sz[2]) + (dp[3]+sz[3]) + (dp[4]+sz[4]) = 5 dp[2] = 0 dp[3] = (dp[5]+sz[5]) = 1 dp[4] = 0 dp[5] = 0 </div> ---- ### 第二次DFS 從根節點開始計算以每個節點為根的距離總和 根節點1到每個節點的距離總和就是 dp[1]  ---- ### 換根 <div style="font-size: 23px"> 從根節點遞迴下去到節點3當根節點 要計算以節點 3 為根的距離為 從根節點方向的距離總和+本身子樹到自己距離總和 </div>  ---- #### 從根節點方向的距離總和 在從根節點遞迴時傳下來 (節點 1 的 dp 值) + (節點 3 的貢獻) - (從根節點方向的節點從節點 1 多走到節點 3 的距離) dp[1] - (dp[3]+sz[3]) + (n-sz[3]) #### 本身子樹到自己距離總和 即為 dp[3]  ---- ### 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<<tot<<endl; } ``` --- ## 啟發式合併 ### (Disjoint Set Union-find on tree) 並查集一般寫法下 單筆操作複雜度為 $O(alpha(n))$ 趨近於常數 而持久化並查集不能路徑壓縮，使得單筆操作複雜度提升到 $O(N)$ 因此要使用啟發式合併來降低複雜度，單筆操作複雜度為 $O(lgN)$ ---- ### 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]); } ``` ---- ### 啟發式合併 在直覺上 每次合併兩個集合時， 把小的集合往大的集合合併 ---- 以節點 1 為根的集合 與 節點 5 為根的集合合併  ---- 把高度較小的合併到高度較大的  合併後高度為 2 ---- 把高度較大的合併到高度較小的  合併後高度為 3 ---- 因此合併時用高度判斷可以降低 find() 函數找根節點的時間 但降低多少? 來看看兩種極端的 case ---- ### (1) 當兩邊樹高不同時，把高度小的合併到高度大的不會增加高度 <div style="position: absolute; right: 70%; top:100%;">  </div> <div style="position: absolute; right: 10%; top:100%;">  </div> ---- ### (2) 當兩邊樹高相同時，高度會增加 <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(NlgN)$ 合併順序：黑色邊 $\to$ 紅色邊 $\to$ 綠色邊 每次合併都是相同高度的樹，高度都會+1 而這種情況高度每+1，節點數量都會變兩倍 因此高度為 h 的樹，會有 $2^h$ 個節點  反推回來，如果有 $N$ 個節點，最高高度為 $lgN$ 而會發現其實最差情況用高度和節點數量去判斷會等價 因此我們通常使用子樹大小去判斷 ---- 因此透過每次小的集合合併到大的集合 最差複雜度為 $O(NlgN)$ ```cpp= int f[MXN], sz[MXN]; // 多紀錄子樹大小 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; } ``` ---- ## 樹上啟發式合併 #### 例題 - Lomsat gelral 給一棵大小為n(n<=1e5) 的有根樹 每個節點上都有塗上一種顏色 問以 1~n 為根的子樹中，出現最多次的顏色數量為何？ #### 作法 當需要用到子樹的資訊，每次去合併時 如果每次都把小的合併到大的，最差複雜度 $O(NlgN)$ ---- 用一個map紀錄不同顏色的數量 最差情況：每個節點顏色都不同 啟發式合併 $O(NlgN)$ * map複雜度 $O(lgN)$ 複雜度為 $O(NlgNlgN)$ 各種實作方法：https://codeforces.com/blog/entry/44351 --- ### 樹上路徑詢問、修改 Q 筆操作 - 詢問點 $u$ 到點 $v$ 路徑上的權重總和 - 更新點 $u$ 到點 $v$ 路徑上的權重加值 如果只有第一種操作可以用 LCA 做 如果只有第二種操作，最後詢問每個節點的權重總和? ---- ### 樹上差分 給你一棵樹，樹上每個節點一開始權重為 0 Q筆操作，每次操作給你一條節點 $x$ 到節點 $y$ 的路徑， 在這條路徑上的每個節點加值 $v$ 最後問你每個節點的值為多少? ---- ### 樹上差分  假設是節點9到節點5的路徑 可以用一個陣列紀錄加值 cnt[9] += v cnt[5] += v 以及在 lca 紀錄減值 cnt[lca(5,9)] -= v cnt[fa[lca(5,9)]] -= v ----  代表 從 9 往上的路徑每個點都要加 v，從 5 往上的路徑每個都要加 v 一直加到 lca 為止，而到 lca 會加兩次(從5、9)，因此要扣掉一次 接著在把 lca 的父節點把剩下的一次再扣掉以免加到沒走到的路徑 ----  加值後從子樹遞迴回來，從節點 9 開始紀錄加的值並往上回傳 ```cpp= int dfs(int x,int f){ int ret = cnt[x]; for(int i:edge[x]){ if(i == f) continue; ret += dfs(i, x); } ans[x] = ret; return ret; } ``` ---- Q 筆操作，每次為其中一種操作 - 詢問點 $u$ 到點 $v$ 路徑上的權重總和 - 更新點 $u$ 到點 $v$ 路徑上的權重加值 ---- ## 樹鏈剖分 ### (Heavy Light Decomposition) <div style="font-size:25px"> 樹鏈剖分，將樹分成很多條鏈， 對每一條鏈用資料結構去維護(如線段樹、樹狀數組之類) 有兩種剖分的方法：長鏈剖分、輕重鏈剖分 由於長鏈剖分不太會出現，且複雜度較差(每次經過最多 $\sqrt{N}$ 條鏈) 所以這邊只介紹輕重鏈剖分(每次經過最多 $lgN$ 條鏈) </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> ----  此棵樹會分成 5 條鏈 [1, 2, 5, 6, 11], [3, 9 ,10], [4, 12], [7], [8] 再把每條鏈分別當成一個序列，對序列建成線段樹、BIT等資料結構 ----  當要路徑更新或路徑加值時，以節點8-節點12的路徑為例 會更新到 [8,3,1,4,12] 5個節點 也就等於更新到四段區間 [8-8] [3-3] [1-1] [4-12] 從詢問的節點所屬的鏈開始更新，接著往上一條鏈更新 直到更新到高度最低的節點為止 ----  另一個例子，節點9-節點6的路徑 更新到 [9,3,1,2,5,6] 6個節點 等於更新到兩個區間 [9-3] [1,6] 兩段 ---- ### 最多會經過幾條鏈?  假設當前鏈的節點數量為 $k$， 更新或詢問時要移動到上一條鏈，代表父節點的子節點中 必定有另一個子節點其子樹 $\ge k$，因此每次往上的子樹大小必定 $\ge 2k+1$ 每次都至少變2倍，到根節點最多不會超過 $lgN$ 條 ---- ### 複雜度 #### 預處理 $O(N)$ 樹鍊剖分 + $lgN$ 條鏈每條花 $O(N)$ 建線段樹 #### 操作 Q筆操作，每次更新/詢問最多經過 $lgN$ 條鏈 而每次資料結構更新/詢問複雜度 $lgN$ #### 總複雜度 $O(NlgN + QlgNlgN)$ ---- 作法 - 兩次DFS: 1. 找重兒子 2. 樹鏈剖分 3. 對每條鏈建資料結構 ---- ### 第一次 dfs 記錄子樹大小、深度、父節點、重兒子等資訊 子樹大小 找重兒子時候用 深度 建資料結構時，建立 index 父節點 在遍歷鏈的時候會用到 重兒子 用於樹鏈剖分 ```cpp= int sz[MXN],dep[MXN],fa[MXN],heavy[MXN]; ``` ---- ### 找重兒子 <div style="margin-left:-180px"> ```cpp= //假設1-base，並且0為指向空節點,sz[0]=0 void dfs1(int x,int f,int d){ dep[x]=d; //紀錄深度 fa[x]=f; //設父節點 sz[x]=1; //將自己本身加進子樹大小 heavy[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[heavy[x]]) heavy[x]=edge[x][i]; //找重兒子 } } ``` </div> ---- ### 記錄每條鏈的資訊  在第二次DFS時計算要建立多少條鏈，以及每條鏈多長 可以知道每條鏈的第一個節點是根節點或者所有的輕兒子 而我們可以用 root 陣列紀錄每個節點所屬的鏈第一個元素是誰 把這條鏈的資訊(長度)都儲存在這條鏈的第一個節點上 ---- ### 樹鏈剖分 <div style="margin-left:-180px"> ```cpp= int treeSz=1; int root[MXN], len[MXN]; void dfs2(int x,int f,bool isLight){ for(int i=0;i<edge[x].size();i++){ if(edge[x][i]==f) continue; if(edge[x][i]==heavy[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> ---- ### 對每條鏈建資料結構 在第二次 DFS 時，有記錄有多少條鏈以及每條鏈的長度 <div style="margin-left:-180px"> ```cpp= vector<int> treeID; vector<vector<int>> tree; void buildTree(){ 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="font-size:24px"> 可以從詢問的兩個節點開始更新區間，直到兩個節點都屬於同一條鏈為止  以節點9到節點7的路徑為例，分別更新各自的鏈，直到兩個節點最後連到同一條鏈為止 每次判斷兩個當前節點的第一節點深度，優先更新較深節點 x = 9, y = 7 y 所屬的鏈第一個節點深度較深dep[3]<dep[7]，更新區間 [7,7]，跳到節點 5 x = 9, y = 5 x 所屬的鏈第一個節點深度較深dep[3]>dep[1]，更新區間 [9,3]，跳到節點 1 接著x, y屬於同一條鏈，更新兩個節點的路徑區間 </div> ---- <div style="margin-left:-180px"> ```cpp= void updatePath(int x,int y,int v){ while(root[x]!=root[y]){ //若不在同一條鏈上 if(dep[root[x]]>dep[root[y]]){ //優先更新深度深的鏈 update(treeID[root[x]],0,dep[x]-dep[root[x]],v); x=fa[root[x]]; } else{ update(treeID[root[y]],0,dep[y]-dep[root[y]],v); y=fa[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> ---- ### 複雜度分析 由於剖分的性質，會使任一個點至根結點最多經過$lgN$條鏈， 每條鏈上的詢問、修改為$O(lgN)$ 因此每筆詢問、修改為$O(lgNlgN)$ Q筆詢問則複雜度為$O(QlgNlgN)$ ---- 用樹鏈剖分找最近共同祖先 ```cpp= void getLca(int x,int y){ while(root[x]!=root[y]){ if(dep[root[x]]>dep[root[y]]) x=fa[root[x]]; else y=fa[root[y]]; } return dep[x]>dep[y]?y:x; } ``` <div style="font-size:25px"> 最多經過 $lgN$ 條鏈，因此複雜度為 $O(lgN)$ </div> --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/489957) 提交期限 5/4，下下星期三 23:59 截止