---
tags: Training, 2022WinterTraining, ACP

title: Tree Centroid Decomposition & Tree Hash

type: slide

slideOptions:
# transition: fade
---

<style>
.reveal .slides {
text-align: left;
font-size:33px;
}
</style>

## Centroid Decomposition & Tree Hash

---

## Centroid Decomposition

重心剖分 (樹分治)，透過每次不斷找到當前子圖的重心，重心拔掉再遞迴下去分割的子樹找各自的重心

重心的定義為一棵樹把節點 $G$ 移除之後，其最大的連通塊會是最小的，而我們會稱節點 $G$ 是樹重心。

----

## 如何找到樹重心

先選一個點為根節點，暴力 $O(n)$ 跑過所有節點紀錄每個節點的子樹大小 $s_i$。

假設子樹大小分別為 $s_1, s_2,... s_k$，則父節點方向的子樹大小為 $n - 1 - \sum{s_i}$

樹重心為 max(n-1-$\sum{s_i}, s_1, s_2...s_k)$ 中最小的節點

----

## 重心的性質

- 把重心拔掉之後, 所有子樹的大小會 $\le\frac{n}{2}$

- 一棵樹最多兩個樹重心

----

## 重心剖分

1. 找到樹重心
2. 把樹重心從圖上移除
3. 遞迴下去連到的子圖
4. 如果子圖大小 >1 回到步驟 1


----

找到<span style = "color:red;">樹重心 </span>


----

把樹重心從塗上移除，剩下的子圖分別去找各自的樹重心


----

找到子圖各自的<span style = "color:orange;">樹重心 </span>


----

把樹重心移除，剩下的子圖分別去找個字的樹重心


----

找到各自的<span style = "color:green;">樹重心 </span>


----

## 複雜度

每次把圖從重心分割，每個子圖最大為原本的一半
最多遞迴 $\log N$ 層

$T(n)=\sum T(s_i) + O(n)$

複雜度 $O(N\log{N})$

----

## 重心樹

對於當前這層的重心與下一層子圖的重心連接可以構出一顆重心樹

由於重心剖分的性質，樹高度不超過 $\log n$

 $\to$ 

----

 $\to$ 

----

## 引入例題

CF 342 E. Xenia and Tree

給你 $n$ 個節點的樹，一開始每個點都是藍色，會有 $m$ 次操作

- 把某個藍點塗成紅色
- 查詢某個點最近的紅點有多遠。

$n, m\le 10^5$

----

$n, m\le 10^5$

如果暴力做，直接用一個陣列紀錄每個節點的顏色

- 把某個藍點塗成紅色 $\to$ O(1) 更新某個節點的顏色

- 查詢某個點最近的紅點 $\to$ BFS 找最近的紅色節點 $O(n)$

很明顯如果每次都是第二種操作，總複雜度為 $O(nm)\to$ TLE

----

### 換一種作法

先選一個節點為根
每個節點紀錄到子樹中最近的紅色節點距離，沒有則視為無限大

1. 把某個藍點 $v$ 塗成紅色
- 從當前節點 $v$ 開始往根節點方向更新所有祖先的距離


----

2. 查詢某個點 $v$ 最近的紅點
- 從當前節點 $v$ 開始往上走
- 每次判斷到某個祖先 $u$ 的距離 + 祖先 $u$ 到他最近的子樹紅色節點距離取最短的


----

1. 把某個藍點 $v$ 塗成紅色
- 從當前節點 $v$ 開始往根節點方向更新所有祖先的距離

2. 查詢某個點 $v$ 最近的紅點
- 從當前節點 $v$ 開始往上走
- 每次判斷到某個祖先 $u$ 的距離 + 祖先 $u$ 到他最近的子樹紅色節點距離取最短的

以上兩種 case 只要到根節點距離很遠複雜度就變 $O(n)$

一樣最差會變成 $O(nm)$

----

### 但如果樹是平衡的 ?

如果樹高最高為 $\log n$

1. 把某個藍點 $v$ 塗成紅色
- 從當前節點 $v$ 開始往根節點方向更新所有祖先的距離

2. 查詢某個點 $v$ 最近的紅點
- 從當前節點 $v$ 開始往上走
- 每次判斷到某個祖先 $u$ 的距離 + 祖先 $u$ 到他最近的子樹紅色節點距離取最短的

則複雜度變成 $O(m \log n)$

----

## 用剛剛的重心樹 ?

會發現重心剖分建出來的重心樹樹高最差為 $\log n$

 $\to$ 

----

### 把節點 $v$ 塗成紅色

用 mn 陣列紀錄子樹中最近的紅色節點距離，沒有則視為無限大

對於每一次塗色，從當前節點往祖先方向走到重心樹根節點
更新從塗色節點 $v$ 到當前走訪到的節點 $u$ 距離是否為更近的紅色節點
mn[u] = min(mn[u], dis(u, v))

----

以塗色節點 5 為例
 

會更新節點 5, 4, 1 到紅色的最短

----

### 詢問節點 $v$ 到最近紅色節點距離

從當前節點往重心樹根節點方向走
每次問走訪到的節點 $u$ 與詢問節點 $v$ 的距離+走訪到的節點 $u$ 到子樹中最近的紅色節點距離
ans = min(ans, dis(u, v) + mn[u])

----

詢問節點 7 到紅色最短
 

答案會是

min( 節點 7 到最近紅色點距離, 
     節點 1 到最近紅色點距離 + 節點 1 到節點 7 的距離)
= min(∞, 2+2) = 4

----

### 為甚麼這樣是好的 ?

只更新從當前節點到重心樹根結點路徑上的距離，其他節點呢 ?

可以分成兩種 case :

1. 最近的紅色節點在重心樹的子樹中
2. 最近的紅色節點在往根節點方向

----

#### 1. 最近的紅色節點 $u$ 在重心樹的子樹中

如果節點 $u$ 在詢問節點 $v$ 的子樹中
則在塗色時已經更新過詢問節點 $v$ 到最近紅色節點的距離

因此答案為 mn[v] = dis(u, v)

----

#### 2. 最近的紅色節點 $u$ 在往根節點方向

則到最近的紅色節點必定會先經過詢問節點 $v$ 的某個祖先 $a$
因此答案為祖先 $a$ 的子樹中最近的節點 + 自己到祖先 $a$ 的距離

mn[a] + dis(a, v)

----

### 複雜度

每次會從當前節點走到重心樹的根節點
每次會計算樹上兩點之間的距離更新最近距離

由於樹高不超過 $\log n$

算樹上兩點之間的距離可以 $O(\log n)$ 找 lca，
再透過深度 dep[u]+dep[v]-2*dep[lca] 得到

因此每次操作的複雜度為 $O(\log^2n)$
總複雜度為 $O(m\log ^2n)$

----

### 細節

注意計算距離是算原本那棵樹上的距離

----

### 另外一個例題

CSES. Fixed-Length Paths I

給一棵 $N$ $(1\le N\le 2\cdot 10^5)$ 個節點的無根樹，樹上有幾個點對的距離為 $k$

也就是有幾個長度為 $k$ 的簡單路徑

----

### 考慮分治

選一個點 $v$ 計算所有經過他且長度為 $k$ 的路徑
把點 $v$ 拔掉再分成各自的連通子圖遞迴下去計算長度為 $k$ 的路徑

----


經過當前點 $v$ 的且長度為 $k$ 的路徑分成兩種

1. 以當前點 $v$ 為起點往外的路徑
2. 經過當前點 $v$ 的且不為起始點的路徑

----

1. **以當前點 $v$ 為起點往外的路徑**

第一種我們可以從點 $v$ 開始 DFS 紀錄從點 $v$ 到當前節點的長度，如果長度為 $k$ 則答案 + 1

auto dfs = [&](int x, int f, int d) -> void{
    if(d == k)     ++ans;
    for(int i : edge[x]){
        if(i == f || vis[i])    continue;
        dfs(i, x, d+1);
    }
};
for(int i : edge[v]){
    dfs(i, v, 1);    // 遞迴從 v 連出去的節點 i
}

----

2. **經過當前點的且不為起始點的路徑**

第二種等價於從點 $v$ 開始往兩棵相異子樹方向長度分別為 $a, b$
且 $a+b = k$ 的路徑

我們可以算往某個子樹長度為 $a$ 的路徑有幾個，乘上往其他子樹路徑長度為 $k-b$ 有幾個。 每個子樹都去計算即為答案

----

每次從點 $v$ 開始往不同的子樹去遞迴，計算每個子樹當前走到的距離 $d$ 與前面計算過有幾個距離為 $k-d$ (儲存在 cnt 陣列裡)

算完之後再把當前子樹的距離加進去 cnt 陣列裡

auto dfs = [&](int x, int f, int d, bool add) -> void{
    if(d == k){    //case 1
        ans++; return;
    }
    if(add)    ans += cnt[k - d];
    else       cnt[d]++;
    for(int i : edge[x]){
        if(i == f || vis[i])    continue;
        dfs(i, x, d+1, add);
    }
};
fill(cnt, cnt+sz, 0);
for(int i : edge[v]){
    dfs(i, v, 0, 0);    // 計算完當前子樹的距離與前面窮舉過的距離加進答案
    dfs(i, v, 0, 1);    // 把當前子樹的距離存進去 cnt 
}

----

每次選一個節點 $v$ 計算經過他且長度為 $k$ 的路徑
再把節點 $v$ 要怎麼選會是最好的 ?

每次選節點 $v$ 計算長度為 $k$ 的路徑複雜度最差為 $O(n)$
如果選重心?

----

回想一下重心剖分的複雜度計算

$T(n)=\sum T(s_i) + O(n)$

每次會跑過當前連通塊所有節點，找到重心之後把重心拔掉
再繼續遞迴下去

---

## Tree Hash

根據樹的形狀把整棵樹 Hash 成一個值。
進而可以 `O(1)` 判斷兩棵樹是否為同構

----

## isomorphism

同構圖的定義為給定兩張圖其節點數量相同，且在兩張圖重新編號後能夠使得任兩個點對其連邊狀況相同

 

上兩張圖為同構圖，把左邊那張編號為 3, 4 的節點交換編號後，其任一點對連邊狀況相同

----

## Rooted Tree Hash

給定兩棵有根樹，判斷是否為同構的有根樹

 

以上為同構有根樹，每個節點的子節點可以重新排列順序後相同

----

## 作法

rolling hash on tree

hash(u) = $\sum$ hash$(v)\times p^i$ % mod

1. 算出每個子樹 $v$ 的 hash 值
2. 把所有子樹 $v$ 的 hash 值排序
3. 依序把每個子樹 $v$ 的 hash 值加入計算

*葉節點的 hash 值為 1

----

1. 算出每個子樹的 hash 值
2. 把所有子樹的 hash 值排序
3. 依序把每個子樹的 hash 值加入計算

ll dfs(int u){
    vector<ll> h;
    subtree_sz[u] = 1;
    for(ll child : edge[u]){
        h.push_back(dfs(child));
        subtree_sz[u] += subtree_sz[child];
    }
    sort(h.begin(), h.end());
    ll ret = subtree_sz[u];
    for(ll v : h){
        ret = (ret * base + v) % MOD;
    }
    return ret;
}

~~如果過不了就多拿幾個參數 hash，反正通常都在亂做~~

----

## 複雜度

每個節點只遍歷一次，每次只排序自己的子節點 hash 值

$O(NlgN)$

----

### 2020 ICPC Taipei region --- Problem G. Graph Cards

判斷有幾種不同構的水母圖 (簡單環 + 環上點連出去樹 )


- $\sum n\le 10^6$

----

## 作法

先找環
相信大家都會做 ?

----

## 作法

把環上連出去的樹分別去做 hash
把所有環上的每棵樹縮點成整棵樹的 hash 值
題目轉換等價於求 幾種不同構的環狀序列

----

幾種不同構的環狀序列 ?

[minimum rotation](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/minRotation.cpp) !

轉一下序列，把序列變成最小字典序為開頭
即可比較兩個環狀序列是否相同

模板 minimum rotation 可以 $O(N)$ 做到求出最小字典序旋轉
函數會回傳要把哪個位置當成開頭
內建函數 rotate() 可以幫你旋轉不用自己轉

---

## 無根樹判斷同構?

由於一棵樹的重心最多只有兩個，因此我們可以直接用重心當根
去做有根樹 hash

判斷兩棵樹是否為同構只需要判斷兩個重心的 hash 值是否相同即可

---

### Question Time and Practice

[Homework Link](https://vjudge.net/contest/535249)

提交期限到 1/13 23:59 截止

----

## 本學期課程結束 ! 相信大家都收穫滿滿 ?

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

<div style="position: absolute; right: 10%;">

- Tree
- Lowest Common Ancestor
- DP on Tree
- DSU on Tree
- Heavy-Light Decomposition
- Centroid Decomposion
- Tree hash

- Graph
- BFS/DFS
- Topological Sort
- Shortet Path
- DSU & MST
- SCC/BCC
- 2-SAT
- Eulerian Path
- LCA
- String
- Trie
- Hash
- KMP
- Manacher
- Palindrome tree
- Z value
- Suffix array
- Geometry
- Convex hull construction
- Sweep Line
- Flow & Matching
- Flow Construction
</div>

- Brute Force Search
- Backtracking
- Memory Search
- Meet In the Middle
- Math
- Modulo Operation
- Modular Multiplicative Inverse
- Prime
- Dynamic Programming
- DP on DAG
- Stack / Deque
- Bitmask DP
- 1D/1D Dynamic Programming
- Convex hull optimization
- Data Structure
- Segment Tree
- BIT
- Sparse Table
- Treap
- Persistent Data Structure
- PBDS

- Square Algorithm
- Square Root Decomposition
- Mo's Algorithm
- Game
- SG value
</div>

----

希望大家對於之後演算法設計、程式實作、面試等等都會有幫助
並不是只是一個三學分的課而已

之後在寫程式前都能先好好分析複雜度、想想學過的演算法是否可以用上

祝大家聖誕節快樂 :gift:

----

期末考 1/6 6:30 大家記得來考 : )

考試內容：練習賽題目、這幾周上課內容