changed 2 years ago  
Linked with GitHub

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)

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

(2)

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

因此可以發現兩種情況中，如果每次合併都是第一種
把小的合併到大的，那均攤複雜度為 \(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 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