# 樹的路徑、直徑與重心 Path, Diameter and Centroid
要讀這篇以前請先讀過[樹的基本性質](https://hackmd.io/@ShanC/Trees-Basic-Properties)，樹的專有名詞就不再解釋了。在前面的篇章，我們都是將樹作為一張連通圖的子圖來看待，進而去探討其中的性質。而這篇我們回到樹本身的性質，透過路徑、根節點與葉節點的關係，來探討一些樹上特別的節點
在實作上，這篇延續 [DFS 與 BFS](https://hackmd.io/@ShanC/bfs_dfs) 的變數名稱，有些東西就不解釋囉!!
## 樹上 DFS/BFS
### DFS on Tree
由於樹就是連通無環圖，因此在實作拜訪各節點的演算法時，可以省去布林陣列 `vis[]` 記錄是否拜訪。實作上只需要確保不要走到父節點即可
```cpp
void dfs(int u, int pre){
for(int &v : g[u]){
if(v != pre) dfs(v,u);
}
}
```
### BFS on Tree
因為 BFS 很自然地就可以記錄起點到每個節點的距離，所以直接用它來判斷是否走過應該不為過吧!
```cpp
void bfs(int s){
queue<int> q; q.push(s);
vector<int> d(n + 1, -1); d[s] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(int &v : g[u]){
if(d[v] != -1) continue;
d[v] = d[u] + 1;
q.push(v);
}
}
}
```
## 樹的深度、高度與大小 Depth、Height and Size
給定一棵有根樹，根為 $r$。此樹有許多直觀的計數性質，以下來逐一說明並實作
小提醒 : 有時要注意題目是 $1$-based 還是 $0$-based
### 深度 Depth
深度就是與根的距離，超簡單!! ||所以就不附圖囉!||
#### BFS 實作
```cpp
void bfs(int r){
queue<int> q; q.push(r);
vector<int> d(n + 1, -1); d[r] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(int &v : g[u]){
if(d[v] != -1) continue;
d[v] = d[u] + 1;
q.push(v);
}
}
}
```
#### DFS 實作
```cpp
void dfs(int u, int pre){
for(int &v : g[u]){
if(v == pre) continue;
d[v] = d[u] + 1;
dfs(v, u);
}
}
```
### 高度 Height
一個點的高度為所有子節點中，高度最高者$+1$
#### 舉例說明
如下圖，樹的高度就是根的高度，也就是 $3$
<center>
<img src="https://hackmd.io/_uploads/Byko1TeOxl.png" style="margin: 0 auto; display: block; width: 400px">
</center>
#### 程式實作
求樹高度要用到一點點樹上 DP 的觀念。這邊因為要保證子節點都已經處理完，因此 DFS 比較妥當 (當然你可以用拓樸排序，但是那很||白癡||)
```cpp
void dfs(int u, int pre){
dep[u] = 0;
for(int &v : g[u]){
if(v == pre) continue;
dfs(v, u);
dep[u] = max(dep[u], dep[v] + 1);
}
}
```
### 大小 Size
這邊的大小是指子樹的節點數量，我們可以用一個式子來計算 :
令 $x$ 為任一個樹上的節點，$x$ 的孩子的集合 $\text{child}(x)$
$$
\text{size}(x)=1+\sum_{y\in \text{child(x)}} \text{size}(y)
$$
可以觀察到如果 $y$ 不是葉節點，那就要繼續再代入 $\text{size(y)}$，直到孩子集合為空才會停止。因此這是個遞迴式，可以用 DFS 來解
#### 範例
可以用下圖來算算看各個子樹的大小
<center>
<img src="https://hackmd.io/_uploads/rJdYepldgl.png" style="margin: 0 auto; display: block; width: 400px">
</center>
#### 程式實作
求子樹大小要用到一點點樹上 DP 的觀念。這邊因為要保證子節點都已經處理完，因此 DFS 比較妥當 (當然你可以用拓樸排序，但是那很||白癡||)
```cpp
int dfs(int u, int pre){
sz[u] = 1;
for(int &v : g[u]){
if(v == pre) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
```
## 直徑 Diameter
### 定義
#### 樹直徑 Diameter
給定一棵樹，則直徑為整棵樹最長的距離，即 $\displaystyle \max_{u, v\in V}\mathrm{dist}(u, v)$
#### 外心距 Eccentricity
對任意定點 $r$，定義其**外心距**(eccentricity)為 $\displaystyle e(r)\;=\;\max_{v\in V}\mathrm{dist}(r,v)$
### 演算法
假設樹有 $n$ 個節點，樹存在 $g[~]$ 裡面。這個技巧叫做「換根」，直接給演算法，不解釋
```cpp
pair<int, int> bfs(int s){
int t = s;
queue<int> q;
vector<int> d(n + 1, -1); // 到 s 的距離
q.push(s);
d[s] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
for(int &v : g[u]){
if(d[v] != -1) continue;
d[v] = d[u] + 1;
q.push(v);
t = v;
}
}
return {t, d[t]}; // {最遠葉子, 最遠距離}
}
int find_diameter(int r){
return bfs(bfs(r).first).second;
}
```
### 引理 1（外心距與直徑關係）
令 $D$ 為直徑，對任意樹上的節點 $r$，其外心距 $e(r)$ 滿足 :
$$
\frac{D}{2} \;\le\; e(r) \;\le\; D
$$
#### 證明
取一對直徑的端點 $(u,v)$，則 $\mathrm{dist}(u,v)=D$。由三角不等式，對任意 $r$：
$$
\mathrm{dist}(u,v)
\;\le\;
\mathrm{dist}(u,r) + \mathrm{dist}(r,v)
\;\le\;
e(r) + e(r)
= 2\,e(r)
$$
故 $e(r)\ge D/2$
顯然對任意 $r$，$\displaystyle e(r)=\max_{v\in V}\mathrm{dist}(r,v)\le\max_{x,y\in V}\mathrm{dist}(x,y)=D$
### 演算法正確性
下面給出證明，說明「從任意節點 $r$ 做一次 BFS 找到最遠節點 $a$，再從 $a$ 做一次 BFS，得到的最大距離即為樹的直徑」
#### 證明
#### 第一次 BFS :
從 $r$ 出發，得到外心距最大的節點 $a$，即 $\displaystyle d(r,a) = e(r) \;\ge\; \frac{D}{2}$
#### Claim : $a$ 必然是某條直徑路徑的端點
設 $(u,v)$ 是一對使 $\mathrm{dist}(u,v)=D$ 的直徑端點。由
$$
\mathrm{dist}(r,u) + \mathrm{dist}(r,v) \;\ge\; \mathrm{dist}(u,v) = D
$$
可推得
$$
\max\bigl(\mathrm{dist}(r,u),\,\mathrm{dist}(r,v)\bigr) \;\ge\; \frac{D}{2}
$$
而第一次 BFS 已選出使 $\mathrm{dist}(r,a)$ 最大的 $a$，且 $\mathrm{dist}(r,a)\ge D/2$。因此 $a$ 必為 $\{u,v\}$ 中之一
#### **第二次 BFS：**
既然 $a$ 是某條最長路徑 $(u,v)$ 的端點之一。那麼從 $a$ 出發，BFS 記錄到所有節點的距離，其中到另一端點 $b\in\{u,v\}\setminus\{a\}$ 的距離必為樹的直徑長度 :
$$
\max_{x\in V}\mathrm{dist}(a,x)
= \mathrm{dist}(a,b)
= D
$$
因此第二次 BFS 回傳的最大距離正好是 $D$，證畢
## 重心 Centroid
### 定義 1
以下我們採用演算法式操作的定義 :
> 我們對所有節點 $x\in V$ 執行以下操作 $f(x)$ :
> 1. 刪除節點 $x$，刪除後會出現森林
> 2. 統計每棵樹節點數，並記錄最大值 $m$
> 3. $f(x)$ 的值即為 $m$
>
> 樹的重心為 $c$，$f(c)=\begin{split}\min_{x\in V}f(x)\end{split}$
### 樹重心舉例說明
如下圖，$f(1)=\max\{4\}=4$、$f(2)=\max\{1, 3\}=3$、$f(3)=\max\{2, 1, 1\}=2$、$f(4)=\max\{4\}=4$、$f(5)=\max\{4\}=4$
取最小之後，答案為 $3$，因為 $f(3)$ 最小
<center>
<img src="https://hackmd.io/_uploads/SkPl29bOxx.png" style="margin: 0 auto; display: block; width: 400px">
</center>
### 根據定義 1 實作演算法
演算法有點複雜，因此我們分步驟討論
#### 說明
根據前面的定義，可以觀察到刪除節點 $x$ 會出現森林。我們觀察刪除節點後的結構，會發現有一棵原本是 $x$ 頭上的樹 (若 $x$ 是根就沒有)，其他均為原本的子樹。如下圖，$f(x)=\max\{|T_a|, |T_b|, |T_c|\}=\max\{3, 2, 1\}=3$ 為最小，因此 $x$ 是重心
<center>
<img src="https://hackmd.io/_uploads/rkSGQYW_eg.png" style="margin: 0 auto; display: block; width: 400px">
</center>
因此，要計算 $f(x)$ 我們不難得出以下步驟 :
1. 取所有子樹大小的最大值 $m'$
2. $m'$ 跟頭上的節點比較得到 $m$
接下來遍歷所有 $x\in V$ 就可以得到答案
#### 尋找子樹大小
這一步就跟[前面](#大小-Size)一樣
```cpp
int dfs(int u, int pre){
sz[u] = 1;
for(int &v : g[u]){
if(v == pre) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
```
#### 計算 $f(x)$
$x$ 頭上的樹的大小其實就是去掉 $x$ 為根的子樹後的大小，也就是 $\max\{m, n - sz[x]\}$，其中 $n$ 為整棵樹的節點數
```cpp
int f(int x, int pre){
int m = 0;
for(int &child : g[x]){
if(child == pre) continue;
m = max(m, sz[child]);
}
m = max(m, n - sz[x]);
return m;
}
```
#### DFS 遍歷
再次強調，因為這是拜訪整棵樹，所以可以省略 `vis[]`，只需要判斷是否為父節點即可
```cpp
int cent_sz = INF, cent; // cent_sz: 大小, cent: 重心
void find_centroid(int u, int pre){
int ans = f(u, pre);
if(cent_sz > ans){ // 取最小值
cent_sz = ans;
cent = u;
}
for(int &v : g[u]){
if(pre == v) continue;
find_centroid(v, u);
}
}
```
#### 作法一
把上面材料組合在一起就可以得到 :
```cpp
int n, cent_sz = INF, cent;
int dfs(int u, int pre){ // 這個先預處理
sz[u] = 1;
for(int &v : g[u]){
if(v == pre) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
int f(int x, int pre){
int m = 0;
for(int &child : g[x]){
if(child == pre) continue;
m = max(m, sz[child]);
}
m = max(m, n - sz[x]);
return m;
}
void find_centroid(int u, int pre){ // 要找的時候呼叫這個
int ans = f(u, pre);
if(cent_sz > ans){
cent_sz = ans;
cent = u;
}
for(int &v : g[u]){
if(pre == v) continue;
find_centroid(v, u);
}
}
```
### 引理 1
若 $c$ 是重心，則將樹以 $c$ 為根，對任一子樹 $T_i$，其節點數 $|T_i|$ 都有 $|T_i| \;\le\; \bigl\lfloor\tfrac{n}{2}\bigr\rfloor$
<center>
<img src="https://hackmd.io/_uploads/B110PWEdxx.png" style="margin: 0 auto; display: block; width: 400px">
</center>
#### 證明
以下證明採用反證法
**假設**
假設存在一個子樹 $T_j$ 滿足 $|T_j| > \lfloor n/2\rfloor$
那麼，刪除根節點 $c$ 後，這個連通塊大小為 $|T_j| > n/2$，所以
$$
f(c)\;\ge\; |T_j|\;>\;\frac{n}{2}
$$
**觀察子節點**
取 $T_j$ 中緊鄰 $c$ 的那條邊上的節點，記作 $u$
刪除節點 $u$ 時，原本與 $c$ 連通的「其餘 $n-|T_j|$ 個節點」會形成一個連通塊，其大小為
$$
n \;-\; |T_j|\;<\;n - \frac{n}{2} \;=\;\frac{n}{2}
$$
其他任何連通塊都屬於 $T_j$ 被切斷後的小塊，其大小必然小於 $|T_j|$，因此
$$
f(u)\;=\;\max\bigl(\,n-|T_j|,\;\text{「其他小連通塊」}\bigr)<\frac{n}{2}<f(c)
$$
**得到矛盾**
根據重心定義，因 $c$ 是所有節點中 $f(\cdot)$ 最小的，所以
$$
f(c)\;\le\;f(u)
$$
但上面卻推得 $f(c)>f(u)$，矛盾
由反證法可知，不可能存在任何子樹大小超過 $\lfloor n/2\rfloor$。因此，若 $c$ 是重心，則以它為根時，每棵子樹的節點數都 $\le \lfloor n/2\rfloor$
**證畢**
### 引理 2
將樹以 $c$ 為根，若對任一子樹 $T_i$，其節點數 $|T_i|$ 都有 $|T_i| \;\le\; \bigl\lfloor\tfrac{n}{2}\bigr\rfloor$，則 $c$ 為重心
#### 證明
令樹的節點數為 $n$。把樹以 $c$ 為根，並假設對每一個子樹 $T_i$ 皆有
$$
|T_i|\le \left\lfloor\frac{n}{2}\right\rfloor
$$
我們要證對任意 $x\in V$ 有 $f(c)\le f(x)$
**(1) $f(c)$ 的上界**
刪掉 $c$ 後，森林剛好是這些子樹 $T_i$，因此
$$
f(c)=\max_{i\in I} |T_i| \le \left\lfloor\frac{n}{2}\right\rfloor\text{ , for some index } I
$$
**(2) 對任意另一點 $u\neq c$，下界估計 $f(u)$**
考慮任意 $u\neq c$。在以 $c$ 為根的樹上，沿從 $c$ 到 $u$ 的路徑，設 $v$ 為這條路徑上緊鄰 $c$ 的第一個節點 (即 $v$ 是 $c$ 的某個 child，且 $u$ 在子樹 $T_v$ 內)。由假設，該子樹大小
$$
|T_v| \le \left\lfloor\frac{n}{2}\right\rfloor
$$
當刪去節點 $u$ 時，樹會被分成若干連通塊。其中有一個塊是**包含 $c$ 的連通塊**，這個連通塊至少包含整個樹中除了整個子樹 $T_v$ 外的所有節點。因此，刪掉 $u$ 後包含 $c$ 的那個連通塊的節點數至少是
$$
n - |T_v|
$$
因此
$$
f(u) \;\ge\; n - |T_v| \;\ge\; n - \left\lfloor\frac{n}{2}\right\rfloor \;=\; \left\lceil\frac{n}{2}\right\rceil
$$
<center>
<img src="https://hackmd.io/_uploads/SJQ_rGE_xg.png" style="margin: 0 auto; display: block; width: 400px">
</center>
**(3) 比較 $f(u)$ 與 $f(c)$**
由 (1) 與 (2) 得到 :
- $f(c) \le \lfloor n/2\rfloor$
- 對任意 $u\ne c$， $f(u) \ge \lceil n/2\rceil$
注意到對所有整數 $n$ 有 $\lceil n/2\rceil \ge \lfloor n/2\rfloor$，因此對任意 $u\neq c$ :
$$
f(u) \ge \lceil n/2\rceil \ge \lfloor n/2\rfloor \ge f(c)
$$
這表示 $f(c)$ 是所有 $f(x)$ 中的最小者，也就是 $c$ 是重心，證畢
### 定理 1
將樹以 $c$ 為根，對任一子樹 $T_i$ 節點數 $|T_i|$ 都有 $|T_i| \;\le\; \bigl\lfloor\tfrac{n}{2}\bigr\rfloor$ 若且為若 $c$ 為重心
#### 證明
根據[引理 1](#引理-1) 與[引理 2](#引理-2)，分別證明相反方向，得證
PS : 由於這個定理與原本的定義等價，因此也有人把這拿來當定義
### 定理 2
從任意點 $x$ 沿著通往重心 $c$ 的方向移動，$f(x)$ 會 non-increasing，並在到達 $c$ 時達到最小值
#### 證明
其實不難觀察出這個結論，光是從[上面的例子](#樹重心舉例說明)就可以看得出這個性質。這部分就留給讀者自己練習
### 根據定理 1 實作演算法
>將樹以 $c$ 為根，對任一子樹 $T_i$ 節點數 $|T_i|$ 都有 $|T_i| \;\le\; \bigl\lfloor\tfrac{n}{2}\bigr\rfloor$ 若且為若 $c$ 為重心
#### 作法二
有了上述的性質，我們可以得到另外一個版本的實作方式。每次找「刪去節點 $u$ 時，判斷是不是所有子樹都小於 $\bigl\lfloor\tfrac{n}{2}\bigr\rfloor$」。換句話說，可以直接去確認 $f(u)$ 是否小於 $\bigl\lfloor\tfrac{n}{2}\bigr\rfloor$，因為若最大的子都比 $\bigl\lfloor\tfrac{n}{2}\bigr\rfloor$ 小，那肯定所有的子樹都比 $\bigl\lfloor\tfrac{n}{2}\bigr\rfloor$ 小
這邊假設你已經學怎麼找子樹大小和上面的一坨東西，所以直接寫在同一個函式裡面
```cpp
int cent; // 這就是重心
void dfs(int u, int pre){
sz[u] = 1;
int mx = 0;
for(int &v : g[u]){
if(v == pre) continue;
dfs(v, u);
sz[u] += sz[v];
mx = max(mx, sz[v]);
}
mx = max(mx, n - sz[u]);
if(mx <= n / 2) cent = u;
}
```
#### 作法三
根據引理 2，令 $r$ 為根，則若存在 $|T_i| \ge\bigl\lfloor\tfrac{n}{2}\bigr\rfloor$，則重心存在於子樹 $T_i$，所以直接找這棵樹即可
<center>
<img src="https://hackmd.io/_uploads/rk1J_GEugg.png" style="margin: 0 auto; display: block; width: 400px">
</center>
`get_cent()` 會直接回傳答案。這樣子找，相當於從根節點移動到重心
```cpp
int dfs(int u, int pre){ // 這個先預處理
sz[u] = 1;
for(int &v : g[u]){
if(v == pre) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
int get_cent(int u, int pre){
for(int &v : g[u]){
if(v != pre && sz[v] > n / 2)
return get_cent(v, u);
}
return u;
}
dfs(1, 0);
ans = get_cent(1, 0);
```
### 時間複雜度
因為三個版本的作法都是 DFS，所以是 $O(n)$。要注意的是，因為處理的對象是樹，樹的邊數都是 $n-1$ 條邊，基本和節點數 $n$ 是同一個量級
值得注意的是，[作法三](#作法三)的 `get_cent()` 每次都挑最大的子樹而直接省去找其他子樹的時間，所以 `get_cent()` 本身是平均是 $O(\log n)$，但最差仍然是 $O(n)$。這對於需要一直做重心查詢的題目可以節省一點時間，像是以下的[重心剖分](#重心剖分-Centroid-Decomposition)
<!-- ### 重心的距離性質 -->
## 重心剖分 Centroid Decomposition
因為重心有良好的[性質](#性質) :
>若 $c$ 是重心，則將樹以 $c$ 為根，對任一子樹 $T_i$，其節點數 $|T_i|$ 都有 $|T_i| \;\le\; \bigl\lfloor\tfrac{n}{2}\bigr\rfloor$
也就是說在刪除 $c$ 之後，所有樹的大小都會小於等於原本的一半，這個性質非常適合拿來做分治法 : 「每次找出重心後，將其刪除，樹會分割成森林。森林中的每棵樹又可以再找新的重心。」因為樹的重心會保證每棵子樹的大小都小於一半，因此分治法可以把時間壓到 $O(n\cdot \log n)$。這類型題目通常很實作，我都交給隊友，所以我自己通常也不太會解
這技巧就是一個 divide 的技巧，至於要怎麼 conquer 跟 combine 要看自己的實作技巧跟經驗
### 演算法流程概述
這篇就提供一個大概的說明，因為這東西太實作了，每次寫出來都長不一樣
> 1. 找重心：一次 DFS 算子樹大小，再沿「大兒子」追下去
> 2. 處理經過重心的答案：
> - 收集每個子樹中，以重心為源的距離分布 : `cnt[d]` 代表距離為 `d` 的數量
> - `cnt[0]=1` 表示重心本身
> - 先查詢再加入：取適當的 `cnt` 加入答案
> 3. 清理暫存：只清到本層用到的最大深度
> 4. 切掉重心，遞迴剩餘子樹
> 5. 停止條件：子樹空或單點
### 複雜度分析
- 層數每次剖半 : $O(\log n)$
- 每層成本 : 找重心 $O(n)$、距離收集 $O(n)$
總時間複雜度 : $O(n\cdot \log n)$
### 常見題型
- **固定長度路徑 / 距離計數 (如「長度恰為 $k$ 的路徑數」)**
想法 : 距離陣列 `cnt[d]`，查詢後再加入
- **距離不超過 $k$ 的點對數**
想法 : 如上，改成前綴累加
- **條件限制 (顏色/屬性)**
想法 : `cnt` 變多維或分顏色維護；順序仍是「查詢 → 加入」
### 例題說明 : [CSES Fixed-Length Paths I](https://cses.fi/problemset/task/2080)
#### 題目
給一棵樹有 $n$ 個節點，求長度恰為 $k$ 的路徑數
#### 限制
- $1 \le k \le n \le 2 \cdot 10^5$
- $1 \le a,b \le n$
#### 題解
考慮重心剖分來將問題拆解成子問題，以下都是實作細節，沒什麼好說的
- `mx_dep` : 當前重心所用到的最大深度，用來限制清空 `cnt[]` 的範圍
- `cnt[d]` : 對「已處理過的子樹」中，距離當前重心為 `d` 的節點數；初始 `cnt[0]=1`
- `cal_cnt()`：
- 目的 : DFS 收集「從當前重心出發」至某子樹所有節點的距離 `d`，並依情境查詢 or 填表。
- 參數 :
`u` : 目前 DFS 的節點
`pre` : 避免走回頭邊到父節點
`filling = false` : 查詢階段 `ans += cnt[k - dep]`
`filling = true` : 填表階段 `cnt[dep]++`
`dep`：從重心的鄰居開始，預設 `1` (重心本身視為距離 `0`，已由 `cnt[0]=1` 表示)
- 剪枝 : 若 `dep > k`，則不可能再配對出長度恰為 `k` 的路徑 (因為距離只能增加)，直接返回
- `decomp()`：
核心步驟 (針對包含 `u` 的當前子樹)：
1. 用 `get_sz` 計算總大小；用 `get_cent` 找出重心 `cent`
2. 標記 `cent` 已移除 (當過重心)，避免跨越到其他子樹
3. 針對 `cent` 的每個尚未被移除的子樹 :
a. 先用 `cal_cnt(v, cent, false)`「查詢」貢獻 (避免同子樹內互配)
b. 再用 `cal_cnt(v, cent, true)` 「填表」併入已處理子樹的距離陣列
4. 將本層用到的 `cnt[1..mx_dep]` 歸零，並維持 `cnt[0]=1`，留給下一層使用
5. 對每個未移除的鄰接子樹遞迴 `decomp()`
```cpp
/* 以上略 */
const int MXN = 2e5 + 5;
vector<int> g[MXN];
int n, k, mx_dep;
ll ans = 0;
bool vis[MXN];
int sz[MXN], cnt[MXN] = {1};
// 計算以 u 為根（忽略已移除的重心與父邊）的子樹大小
int get_sz(int u, int pre){ // 這個先預處理
sz[u] = 1;
for(int &v : g[u]){
// 不跨越父親、也不進入已「移除當過重心」的節點
if(v == pre || vis[v]) continue;
sz[u] += get_sz(v, u);
}
return sz[u];
}
// 在包含 u 的當前子樹內找重心 :
// 從 u 出發，若存在子樹大小 >= desired (約 n/2) 就往那個子樹走
// 直到找不到更大的子樹為止，回傳當前節點作為重心
int get_cent(int u, int pre, int desired){
for(int &v : g[u]){
if(v != pre && sz[v] >= desired && !vis[v])
return get_cent(v, u, desired);
}
return u;
}
void cal_cnt(int u, int pre, bool filling, int dep = 1){
if(dep > k) return;
mx_dep = max(mx_dep, dep); // 記錄本層最大深度，供稍後清空 cnt[] 使用
if(filling) cnt[dep]++; // 填表 : 把這個子樹的距離分布，併入「已處理過的子樹」
else ans += cnt[k - dep]; // 查詢 : 找另一側距離是 (k - dep) 的節點數，配對成長度 k
for(int &v : g[u]){
if(!vis[v] && pre != v)
cal_cnt(v, u, filling, dep + 1);
}
}
void decomp(int u = 1){
// 找重心 (若 total 偶數，可能落在任一個重心)
int cent = get_cent(u, 0, get_sz(u, 0) / 2);
vis[cent] = true; // 移除重心，切割成多個子樹
mx_dep = 0; // 重置本層使用過的最大深度
// 針對每個鄰接子樹 : 先查詢、後填表 (避免同一子樹內互相配對)
for(int &v : g[cent]){
if(vis[v]) continue;
cal_cnt(v, cent, false); // 查詢 : 累加所有「經過重心」的長度= k 的路徑
cal_cnt(v, cent, true); // 填表 : 把這個子樹的距離分布併入 cnt[]
}
// 重置 cnt[] : 保留 cnt[0]=1 (代表僅重心)，清掉本層曾經動用過的深度範圍
// 註 : 此實作選擇在「離開當前重心」時做清理，確保下一層剛進來時 cnt 狀態就是正確的
cnt[0] = 1;
for(int i = 1; i <= mx_dep; i++) cnt[i] = 0;
// 遞迴處理每個子樹 (此時重心已被標記，不會跨越到其他分支)
for(int &v : g[cent]){
if(!vis[v]) decomp(v);
}
}
/* 以下略 */
```
## 題目練習
基本上在競程遇到這類問題都是要稍微腦袋轉一下，沒那麼直觀
[Zerojudge f673. FJCU_109_Winter_Day2_Lab1 樹高](https://zerojudge.tw/ShowProblem?problemid=f673) (裸題)
[Zerojudge c463. apcs 樹狀圖分析 (Tree Analyses)](https://zerojudge.tw/ShowProblem?problemid=c463) (有點裸)
[Zerojudge b218. 3. 找關鍵人物](https://zerojudge.tw/ShowProblem?problemid=b218) (子樹大小+算一算)
[Zerojudge b967. 4. 血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967) (裸題)
[CSES Subordinates](https://cses.fi/problemset/task/1674/) (裸題)
[CSES Tree Diameter](https://cses.fi/problemset/task/1131) (裸題)
[CSES Tree Distances I](https://cses.fi/problemset/task/1132/) (直徑的性質，注意到每個點最遠距離會在直徑兩端點，證證看)
[codeforces 1404B. Tree Tag](https://codeforces.com/contest/1404/problem/B)
[codeforces 1294F. Three Paths on a Tree](https://codeforces.com/problemset/problem/1294/F) (已知直徑，怎麼求離直徑的最遠距離呢?)
[codeforces 734E. Anton and Tree](https://codeforces.com/contest/734/problem/E) (DSU + 半徑)
[codeforces 456E. Civilization](https://codeforces.com/contest/456/problem/E) (DSU + 如何構建最短直徑)
[AtCoder Beginner Contest 221 F. Diameter set](https://atcoder.jp/contests/abc221/tasks/abc221_f?lang=en)
[codeforces 761E. Christmas Chocolates](https://codeforces.com/contest/1617/problem/E)
[codeforces 1214H. Tiles Placement](https://codeforces.com/contest/1214/problem/H)
[codeforces 1406C. Link Cut Centroids](https://codeforces.com/contest/1406/problem/C) (這題可以學到關於重心唯一的條件)
[CSES Finding a Centroid](https://cses.fi/problemset/task/2079) (裸題，可以用這題試試看三種找重心的方法)
[codeforces 685B. Kay and Snowflake](https://codeforces.com/problemset/problem/685/B) (半裸題，需要用到重心的定理 2)
[codeforces 321C. Ciel the Commander](https://codeforces.com/contest/321/problem/C)
[CSES Fixed-Length Paths I](https://cses.fi/problemset/task/2080) (裸的重心剖分)
[CSES Fixed-Length Paths II](https://cses.fi/problemset/task/2081) (相信我，BIT會TLE得很慘，update跟query有一堆log)
[codeforces 776F. Sherlock's bet to Moriarty](https://codeforces.com/contest/776/problem/F)
[codeforces 342E. Xenia and Tree](https://codeforces.com/problemset/problem/342/E)
----
## 參考資料
- [[Tutorial] Diameter of a tree and its applications](https://codeforces.com/blog/entry/101271)
- [Proof of algorithm to find the diameter of a tree.](https://codeforces.com/blog/entry/60440)
- [Centers of a tree](https://www.tutorialspoint.com/centers-of-a-tree)
- [Centroid Decomposition of Tree](https://www.geeksforgeeks.org/dsa/centroid-decomposition-of-tree/)
- [海大競程 - 圖上遍歷 & 樹論](https://hackmd.io/@LeeShoWhaodian/I2CP2024tree1#/)
- [台師大演算法筆記 - tree](https://web.ntnu.edu.tw/~algo/Tree.html)
- [USACO - Centroid Decomposition](https://usaco.guide/plat/centroid)
- [OI Wiki - 樹的重心](https://oi-wiki.org/graph/tree-centroid/)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/8/10
Sign in with Wallet
Connect another wallet