---
tags: Training

type: slide

---

<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

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

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)

<div style="font-size: 30px">

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

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

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

</div>

----

### 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]);
}

----

### 啟發式合併

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

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">

//假設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">

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">

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">

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>

----

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

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>