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個點為根的子樹最佳答案

直接來看例題

給你一棵有 \(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

暴力一點

  • \(O(N^3)\)

    窮舉每個點對，DFS暴力兩點的距離

  • \(O(N^2)\)

    每個點當起點DFS，走到每個點把總和記下來

\(O(N)\) 樹DP

DFS 兩次

第一次

找一個點 (這邊以節點1為根) 當根，
算出所有點的子樹到自己的距離總和

第二次

遞迴到每個點順便算每個點到當前點的距離

第一次DFS

算每個節點的子樹到自己的距離總和，以及子樹大小
dp[i] 的定義為以節點i為根的子樹到節點i的距離總和

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

sample code












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

從根節點開始算每個節點到自己的距離總和
根節點1到每個節點的距離總和就是 dp[1]

遞迴下去其他節點

從根結點遞迴下去到節點3，這時我們會傳一個參數下去
從父節點方向來的節點到當前節點距離總和
也就是 (dp[1]-(dp[3]+sz[3])) + dp[3] + (sz[1]-sz[3])

( 父節點方向到節點3的距離總和 + 自己子樹到節點3距離總和 + 父節點方向的節點數量 )

sample code












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)\)







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)

並查集一般寫法下 單筆操作複雜度為 \(O(alpha(n))\) 趨近於常數

而持久化並查集不能路徑壓縮，使得單筆操作複雜度提升到 \(O(N)\)

因此要使用啟發式合併來降低複雜度，單筆操作複雜度為 \(O(lgN)\)

find 函式

路徑壓縮





int find(int x){
    if(f[x] == x)    return x;
    return f[x] = find(f[x]);
}

少了路徑壓縮 最差複雜度為 \(O(N)\)





int find(int x){
    if(f[x] == x)    return x;
    return find(f[x]);
}

啟發式合併

每次合併時，把小的往大的合併
先來看以下兩種極端例子

(1)

其中一邊的樹比另一邊大很多，
當小的合併到大的時候複雜度趨近於常數

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

(2)

當兩邊大小差不多時，
合併的複雜度為 \(O(n)\) (n為樹的大小)

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

因此可以發現兩種情況中，如果每次合併都是第一種
把小的合併到大的，那均攤複雜度為 \(O(N)\)

但如果每次都是第二種，複雜度會變多少?

答案是 \(O(NlgN)\)

因此透過每次小的合併到大的
最差複雜度為 \(O(NlgN)\)












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;
}

用途

當需要用到子樹的資訊，每次去合併時
如果每次都把小的合併到大的，最差複雜度 \(O(NlgN)\)

例題

​​​​給一棵大小為n(n<=1e5) 的有根樹 每個節點上都有塗上一種顏色 
​​​​問以 1~n 為根的子樹中，出現最多次的顏色數量為何？

用一個map紀錄不同顏色的數量

最差情況：每個節點顏色都不同
照子樹大小去合併，複雜度為 \(O(NlgNlgN)\)
啟發式合併 \(O(NlgN)\) * map複雜度 \(O(lgN)\)

記得正常情況下的並查集，只需使用路徑壓縮即可

除非是需要用到 啟發式合併的技巧 或者 持久化並查集
再用啟發式合併

樹鏈剖分

(Heavy Light Decomposition)

有兩種剖分的方法：長鏈剖分、輕重鏈剖分
由於長鏈剖分不太會出現，所以這邊只介紹輕重鏈剖分

顧名思義，將樹分成很多條鏈，
對每一條鏈用資料結構去維護(如線段樹、樹狀數組之類)

樹上路徑詢問、修改
EX：樹上從點\(a\)到點\(b\)的路徑上，詢問總和 or 經過的點加值

名詞介紹

重兒子：每個點的子樹中，子樹大小(即節點數)最大的子節點

輕兒子：除重兒子外的其他子節點

重邊：每個節點與其重兒子間的邊

輕邊：每個節點與其輕兒子間的邊

重鏈：重邊連成的鏈

輕鏈：輕邊連成的鏈

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

image alt

作法 - 兩次DFS:

  1. 找重兒子
  2. 樹鏈剖分
  3. 對每條鏈建資料結構

找重兒子















//假設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];  //找重兒子
    }
}

樹鏈剖分













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]]++;                      //更新每條鏈的長度
}

對每條鏈建資料結構













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倍大小
    }
}

樹鏈剖分完以後，

如何路經修改、詢問?
















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);  //最後會連至同一條鏈上，更新範圍
}

複雜度分析

由於剖分的性質，會使任一個點至根結點最多經過\(lgN\)條鏈，
每條鏈上的詢問、修改為\(O(lgN)\)

因此每筆詢問、修改為\(O(lgNlgN)\)
Q筆詢問則複雜度為\(O(QlgNlgN)\)

用樹鏈剖分找最近共同祖先









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;
}

最多經過 \(lgN\) 條鏈，因此複雜度為 \(O(lgN)\)

Question Time and Practice

Homework Link

提交期限兩星期，下下星期一 18:30 截止

Select a repo