# 最低共同祖先 Lowest Common Ancestor
前面我們講過[倍增法](https://hackmd.io/@ShanC/Binary-Exponentiation-and-Lifting#%E5%80%8D%E5%A2%9E%E6%B3%95%E7%B0%A1%E4%BB%8B)，這篇我們會使用這個方法來實作最低共同祖先。但話說回來，什麼是最低共同祖先呢? 本篇會來好好說明這個東西。接下來會來討論，這個東西可以拿來做什麼。最低共同祖先可以方便我們在對樹上整條路徑做操作，是個好用的工具
## 最低共同祖先 Lowest Common Ancestor
### 複習一些名詞
- 路徑 : 一個節點序列 (有時會看作是一個集合，要看前後文)，之間不會有重複的節點。通常以兩端點表示，如 $a, b\text{-path}$
- 葉節點 : 樹上度數為 $1$ 的節點，每棵樹上一定會有 $2$ 以上片葉子
- 根節點 : 與葉不同，這是一個需要「人為定義」的節點。每個節點 (包含葉) 都可以當作根，而一棵樹只會有一個根。通常寫作 $r$
- 有根樹 : 擁有根節點的樹。**在這篇都是討論有根樹，所以會省略一棵樹是有根樹這件事**
- $x$ 的祖先 : 在 $r, x\text{-path}$ 上，比節點 $x$ 更靠近 $r$ 的節點們 (可能不只一個)
### 共同祖先 Common Ancestors
令有根樹的根為 $r$，對於兩個節點 $x,y$，共同祖先 $\text{CA}(x, y)$ 為 $r,x\text{-path }$ 與 $r,y\text{-path}$ 共同的節點
### 最低共同祖先 Lowest Common Ancestor
令有根樹的根為 $r$，對於兩個節點 $x,y$，最低共同祖先是在 $\text{CA} (x, y)$ 中離 $x$ 與 $y$ 最近的節點 $\text{LCA}(x, y)$。要注意的是，因為在樹當中路徑是唯一的，所以 $\text{LCA}$ 也是唯一
### 舉例說明
由下圖可知，$\text{LCA}(a, b)=x$、$\text{CA}(a, b) = \{x, y\}$
<center>
<img src="https://hackmd.io/_uploads/SJWhAQvdge.png" style="margin: 0 auto; display: block; width: 400px">
</center>
### 樹深度
每個節點的深度就是與根的距離，我們在 DFS/BFS 時就可以順便算出來
```cpp
int dep[MXN];
void dfs_dep(int u, int pre){
for(int &v : g[u]){
if(v == pre) continue;
dep[v] = dep[u] + 1;
dfs_dep(v, u);
}
}
```
## 複習倍增法
還記得[倍增法](https://hackmd.io/@ShanC/Binary-Exponentiation-and-Lifting)嗎? 倍增法會把每個節點 $x$ 的 $2^i$ 代祖先都記在 `anc[x][i]` 裡面，細節請自己去複習之前寫的那篇
### 輸入
有時候我們可以在輸入時就把 `anc[][]` 每個節點父親的部分先建好
```cpp
int anc[MXN][logN]; // MXN: 最大節點數、logN: 最大祖先數
cin >> n; // 輸入節點數量
for (int i = 2; i <= n; i++){
cin >> father >> x; // 輸入 x 的父節點、x
anc[x][0] = father; // 父節點就是 2^0 倍祖先
}
```
### 初始化
這邊就是把「倍增表」建好，使用的是 DP 的技巧
```cpp
// logN: 最大的祖先數
for (int i = 1; i < logN; i++) { // binary lifting
for (int u = 1; u <= n; u++) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
}
```
### 爬 $k$ 步
有些人會把這步寫成 $k\text{-th ancestor}(x, k)$，簡單來說就是從 $x$ 爬到第 $k$ 代祖先
```cpp
int move(int x, int k){
for (int i = 0; i < logN; i++) {
if (k & (1 << i))
x = anc[x][i];
}
return x; // 這裡要注意，若移動超過根，就會回傳 0
}
```
### 注意到
- $r$ 是樹上所有節點的共同祖先
- $x$ 與 $y$ 的共同祖先能在 `anc` 上找到。若 $x$ 與 $y$ 的深度相同，那麼他們同時往上走，會在對低共同祖先碰在一起
如[上圖](#舉例說明)，$y$ 是大家的共同祖先；$a$ 與 $b$ 同時往上走一步會到 $\text{LCA}(a, b)=x$
## 複習時間戳記
時間戳記是 DFS 本身就會有的特性之一，你應該要知道才對，因為在最基礎的[這篇](https://hackmd.io/@ShanC/bfs_dfs#%E6%99%82%E9%96%93%E6%88%B3%E8%A8%98)講過了
### 程式碼實作
我們可以在上述遞迴版本的程式碼中加入:
- $d[i]$: 發現節點 $i$ 的時間 (discovery time)
- $f[i]$ : 節點 $i$ 完成所有鄰居拜訪的時間 (finishing time)
```cpp
void dfs_time(int u, int pre) {
d[u] = ++timestamp; // 紀錄發現時間
for (int &v : g[u]) {
if (v != pre) dfs_time(v, u);
}
f[u] = ++timestamp; // 紀錄結束時間
}
```
我們把[上圖](#舉例說明)跟 $d[i]$、$f[i]$ 結合起來可以得到下圖。我們可以把時間戳記當作是一個計時器
<center>
<img src="https://hackmd.io/_uploads/ByPVHVv_xg.png" style="margin: 0 auto; display: block; width: 600px">
</center>
### 括號定理
當我們把[上圖](#舉例說明)所有節點 $v$ 的發現與結束時間畫在數線上，會形成好幾個區間
<center>
<img src="https://hackmd.io/_uploads/Bkq8VG__gx.png" style="margin: 0 auto; display: block; width: 600px">
</center>
藉由上圖會發現，對於任兩節點 $u$ 與 $v$ 在樹中 :
1. 如果區間 $[d[u], f[u]]$ 包含 $[d[v], f[v]]$，則 $u$ 為 $v$ 的祖先
2. 如果區間 $[d[v], f[v]]$ 包含 $[d[u], f[u]]$，則 $u$ 為 $v$ 的後代
3. 如果區間 $[d[u], f[u]]$ 與 $[d[v], f[v]]$ 沒有交集，則 $u$ 與 $v$ 沒有血緣關係
可以得到推論 : 在一棵樹中，$d[u]<d[v]<f[v]<f[u]$ 若且唯若，$v$ 是 $u$ 的後代
## 如何找最低共同祖先?
### 括號定理確定是否為祖先
根據[括號定理的推論](#括號定理)，我們可以知道該如何查詢任一個節點 $u$ 是不是節點 $v$ 的祖先。由於對於任一點 $x$，$d[x]<f[x]$ 都是確定的，因此只需要確認 $d[u] < d[v]$ 與 $f[v] < f[u]$ 就好。值得注意的是，根據程式碼，若 $d[u]=d[v]$ 那 $f[u]=f[v]$，也就代表 $u=v$。因為在 $u=v$ 的情況下**有時候**也算是彼此的祖先，因此可以將 $<$ 替換成 $\leq$
```cpp
bool is_ancestor(int u, int v){
return d[u] <= d[v] && f[v] <= f[u];
}
```
### 粗暴地往根的方向找
有了確認是否為祖先的方式，那我們就可以來處理找最低共同祖先的問題。給定兩點 $u, v$，我們可以考慮以下方法 :
1. $u$ 往上走，直到 $u$ 成為 $v$ 的祖先
2. $u$ 的位置即為 $\text{LCA}(u, v)$
但是這方法可能會花很多時間，每次最差都要花費 $O(n)$ 的時間
### 引入倍增法
根據[上面](#粗暴地往根的方向找)的想法，我們引入倍增法。實作很簡單，但要理解就很難，程式碼只可意會不可言傳，以下提供給讀者自行體會
```cpp
int getlca(int u, int v){
if (is_ancestor(u, v)) return u; // 如果 u 為 v 的祖先則 lca 為 u
if (is_ancestor(v, u)) return v; // 如果 v 為 u 的祖先則 lca 為 u
for (int i = logN; i >= 0; i--){ // 判斷 2^logN, 2^(logN-1),...2^1, 2^0 倍祖先
if (anc[u][i] &&
!is_ancestor(anc[u][i], v)) // 如果 2^i 倍祖先不是 v 的祖先
u = anc[u][i]; // 則往上移動
}
return anc[u][0]; // 回傳此點的父節點即為答案
}
```
每一次查詢都是 $O(\log n)$ 的時間，比原本 $O(n)$ 好很多
### 直接利用倍增法來找
[上面](#引入倍增法)的方法需要預先跑一次時間戳記的程式才能知道開始與結束時間，進而用來判斷 $u$ 是否為 $v$ 的祖先。事實上我們不需要這麼麻煩。我們原本的目的只是想要找最低共同祖先而已，而我們在[前面已經注意到](#注意到)以下兩點 :
1. 若 $u$ 與 $v$ 的深度相同，則移動相同步數可以同時抵達 $\text{LCA}$
2. 若 $u$ 的深度比 $v$ 深，則可以將 $u$ 移動到相同深度後，回到 1. 的情況
```cpp
int getlca(int u, int v){
if(dep[u] < dep[v]) swap(u, v); // 判斷誰深度最深
u = move(u, dep[u] - dep[v]); // 爬到相同深度
if(u == v) return u; // 如果兩者在相同位置那調表那就是 LCA
for(int i = logN; i >= 0; i--){ // i 從大到小
if(anc[u][i] != anc[v][i]){ // 如果兩者爬 2^i 步仍不相同
u = anc[u][i]; // 倍增法爬到 2^i 代祖先
v = anc[v][i];
}
}
return anc[u][0]; // 父親就是 LCA
}
```
## 程式實作
上面我們寫得太亂了，以下我把它整理成一份模板。由於陣列初始化都為 $0$，所以宣告就不寫了。以下的程式碼與[上面](#輸入)不同，這裡先假設 `anc[][]` 還沒建好
### 方法一 : 用時間戳記判斷其中一點是否為另一點的 LCA
找 LCA 在競程上通常是線上算法，因此最前置作業就是要先初始化 `anc[][]` 與時間戳記 :
1. 先 DFS 一次，把時間戳記與 `anc` 中每個節點的 $2^0$ 代祖先建立好
2. 把倍增表 `anc[][]` 建好
接下來就是呼叫 `getlca()` 請求中，每次要做的事情 :
1. 判斷兩節點 $u$ 是否為 $v$ 的祖先，或著反之 $v$ 是否為 $u$ 的祖先。是的話直接回傳即可 $O(1)$
(這裡有個實作細節，若題目說同一點互為彼此的祖先就要從 $<$ 改成 $\leq$)
2. 接下來，程式移動其中一節點 $u$ (用倍增法從跳比較遠到跳比較近的距離)，判斷他父親是不是 $\text{LCA}$
- 否的話就往上爬
- 是則忽略 (因為如果爬的話有可能超過)
3. 回傳 $u$ 的父親即為 $\text{LCA}$
```cpp
void dfs_time(int u, int pre) { // 時間戳記
d[u] = ++timestamp; // 紀錄發現時間
anc[u][0] = pre; // 這裡就順便紀錄爸爸是誰
for (int &v : g[u]) {
if (v != pre) dfs_time(v, u);
}
f[u] = ++timestamp; // 紀錄結束時間
}
void init(){ // 先執行這個
dfs_time(1, 0); // 假設 1 為根
for (int i = 1; i < logN; i++) { // binary lifting
for (int u = 1; u <= n; u++)
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
}
bool is_ancestor(int u, int v){ // 判斷是否為祖先
return d[u] <= d[v] && f[v] <= f[u]; // 實作細節 : 有可能會遇到同一點的狀況，所以要加 =
}
int getlca(int u, int v){
if (is_ancestor(u, v)) return u; // 如果 u 為 v 的祖先則 lca 為 u
if (is_ancestor(v, u)) return v; // 如果 v 為 u 的祖先則 lca 為 u
for (int i = logN; i >= 0; i--){ // 判斷 2^logN, 2^(logN-1),...2^1, 2^0 倍祖先
if (anc[u][i] &&
!is_ancestor(anc[u][i], v)) // 如果 2^i 倍祖先不是 v 的祖先
u = anc[u][i]; // 則往上移動
}
return anc[u][0]; // 回傳此點的父節點即為答案
}
```
### 方法二 : 先到相同深度再找 LCA
這個方法就不需要時間戳記了，不要忘了時間戳記需要兩個序列 $d[~]$ 與 $f[~]$ 來維護，而這種方法只須要維護一個深度的陣列 `dep[]` 即可，省一點常數空間的同時還可以重複利用 `dep[]` 來計算其他事情，像是[以下就是很好的例子](#LCA-應用-:-求樹上任意兩點距離)。這方法的初始化詳細步驟如下 :
1. 跑 DFS，把 `dep[]` 與 `anc` 中每個節點的 $2^0$ 代祖先建立好
2. 把倍增表 `anc[][]` 建好
接下來在 `getlca()` 中 :
1. 先將比較深的節點設為 $u$，淺的設為 $v$
2. 將比較深的節點 $u$ 移到跟 $v$ 相同的高度
3. 若兩節點相同則直接回傳
4. 用迴圈跳倍增法，從遠到近跳 :
- 若兩者的第 $2^i$ 代祖先不相同，則兩節點分別跳到該代祖先
- 否則忽略 (不然會跳超過 $\text{LCA}$)
5. 兩節點的父親即為 $\text{LCA}$，回傳答案
```cpp
void dfs_dep(int u, int pre) { // 求深度
anc[u][0] = pre; // 這裡就順便紀錄每個節點爸爸是誰
for (int &v : g[u]) {
if (v == pre)
continue;
dep[v] = dep[u] + 1;
dfs_dep(v, u);
}
}
void init() { // 先執行這個
dfs_dep(1, 0); // 假設 1 為根
for (int i = 1; i < logN; i++) { // binary lifting
for (int u = 1; u <= n; u++)
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
}
int move(int x, int k){ // 倍增法往上移動 k 步
for (int i = 0; i < logN; i++) {
if (k & (1 << i))
x = anc[x][i];
}
return x; // 這裡要注意，若移動超過根，就會回傳 0
}
int getlca(int u, int v){
if(dep[u] < dep[v]) swap(u, v); // 判斷誰深度最深
u = move(u, dep[u] - dep[v]); // 爬到相同深度
if(u == v) return u; // 如果兩者在相同位置那調表那就是 LCA
for(int i = logN; i >= 0; i--){ // i 從大到小
if(anc[u][i] != anc[v][i]){ // 如果兩者爬 2^i 步仍不相同
u = anc[u][i]; // 倍增法爬到 2^i 代祖先
v = anc[v][i];
}
}
return anc[u][0]; // 父親就是 LCA
}
```
## LCA 應用 : 求樹上任意兩點距離
在之前的章節，要找到圖中兩點距離，可以用 BFS 以其中一點為起點開始遍歷。若今天的情境是每次都要詢問樹上任兩點的距離，那這樣子太慢了
### 推導
假設我們已知深度，設 $\mathrm{lca}=\text{LCA}(a, b)$，即任一點至根的距離 $\mathrm{dist}(r, x)$。若要求兩點距離 $\mathrm{dist}(a, b)$，那麼我們可以推出 :
$$
\begin{split}
\mathrm{dist}(a, b)&=\mathrm{dist}(a, \mathrm{lca}) + \mathrm{dist}(\mathrm{lca}, b)\\
&=(\mathrm{dist}(a, r)-\mathrm{dist}(r, \mathrm{lca}))+(\mathrm{dist}(b, r)-\mathrm{dist}(r, \mathrm{lca}))\\
&=(\mathrm{depth}(a)-\mathrm{depth}(\mathrm{lca}))+(\mathrm{depth}(b)-\mathrm{depth}(\mathrm{lca}))\\
&=\mathrm{depth}(a)+\mathrm{depth}(b)-2\cdot\mathrm{depth}(\mathrm{lca})
\end{split}
$$
### 程式碼實作
```cpp
int dist(int a, int b){
return dep[a] + dep[b] - 2 * dep[getlca(a, b)];
}
```
## LCA 應用 : 樹上差分
大多時候我們在競程的前綴和、後綴和、差分都是在有限的非負整數，但其實我們可以把這種概念抽象化變成一條鏈，每次我們做前綴和、後綴和、差分等操作都是在鏈上。眾所周知，鏈是一種圖。所以我們可以很輕鬆地把前綴和、差分等概念拓展到樹上。我們可以在樹上前綴和、後綴和、差分，因為 :
- 樹上所有點對的路徑都是唯一
- 每個節點的父節點都是唯一
### 樹上前綴和
可以想像，樹就是一條有很多分支的數軸，共通點是都有一個起點叫做根。若賦予每個節點一個權重，我們可以從根節點出發，並且把父節點的值都加進子節點的值。如此一來就可以得到數上前綴和
```cpp
void dfs(int u, int pre){
for(int &v : g[u]){
if(pre == v) continue;
pre[v] += pre[u]; // 樹上前綴和
dfs(v, u);
}
}
```
樹上前綴和的效果大概就如下圖所示
<center>
<img src="https://hackmd.io/_uploads/r1tJmOuOxx.png" style="margin: 0 auto; display: block; width: 600px">
</center>
### 樹上後綴和
從某節點 $u$，一路把值加回到根節點。這執行的順序跟拓樸排序很像
```cpp
void dfs(int u, int pre){
for(int &v : g[u]){ // 樹上每個 v 的父節點都唯一
if(pre == v) continue;
dfs(v, u);
suf[u] += suf[v]; // 樹上後綴和
}
}
```
樹上後綴和的效果大概就如下圖所示
<center>
<img src="https://hackmd.io/_uploads/H1lkEdu_gx.png" style="margin: 0 auto; display: block; width: 600px">
</center>
因數上每個節點都只有一個父親，樹上後綴和的效果只會作用在一條通往根的路徑上
註 : 「樹上後綴和」是我取的名字，為了與樹上前綴和做出區別，不知道為什麼網路上沒人為這個技巧命名，頂多把他歸類在 DP on tree
### 樹上差分
在樹上前綴和，每次都會把權重加到整顆子樹的節點上；樹上後綴和，每次都把權重加到點到根的路徑上的所有節點。但是有時候我們只想要加權重 $w$ 在某條特定 $a, b\text{-path}$ 的節點上，該怎麼辦呢?
前綴和我們不考慮。若對 $a, b$ 分別加值並使用樹上後綴和，那麼會發現以下現象 : $\text{LCA}(a, b)$ 到 $r$ 的路徑上會同時被 $a$ 與 $b$ 的權重加值
<center>
<img src="https://hackmd.io/_uploads/BJXqvuu_xl.png" style="margin: 0 auto; display: block; width: 600px">
</center>
這問題不難解決，多出來的值，減掉就好。不難觀察到，$\text{LCA}(a, b)$ 被多加了一次，其餘從$\text{LCA}(a, b)$ 的父節點到 $r$ 則是被多加兩次。我們可以考慮樹上差分技巧 : 在路徑的兩端點 $a, b$ 加值後，$\text{LCA}(a, b)$ 與 $\text{LCA}(a, b)$ 的父節點各減一次值。如此一來就會對 $\text{LCA}(a, b)$ 到 $r$ 的路徑毫無影響
<center>
<img src="https://hackmd.io/_uploads/BkeRtdd_eg.png" style="margin: 0 auto; display: block; width: 600px">
</center>
因此，若我們想只加權重在某條路徑上，在加值時使用以下這個方法即可
```cpp
void add(int a, int b, ll w){
int lca = getlca(a, b); // 求 LCA(a, b)
suf[a] += w; // a 加值
suf[b] += w; // b 加值
suf[lca] -= w; // lca 減值
suf[anc[lca][0]] -= w; // lca 的父節點減值
}
```
值得注意的是，樹上差分與序列上差分最不同的是，樹上差分是離線算法，無法一邊輸入一邊處理資料，因為時間會炸掉
## LCA 應用 : 次小生成樹 Second Best Minimum Spanning Tree
最小生成樹在[這篇](https://hackmd.io/@ShanC/minimum-spanning-tree)講過了，所以就不前情提要囉!!
### 次小生成樹
次小生成樹簡稱 SBMST。簡單來說就是權重總和第二小的生成樹，沒什麼大不了的。假設我們已經用 Kruskal 演算法求出最小生成樹 $T$，我們要找出一條邊 $e'\notin T$ 與另一條邊 $e\in T$，使得 $T'=(T\setminus\{e\})\cup\{e'\}$ 是一棵生成樹且 $w(e')-w(e)$ 為最小。$w(T')$ 是次小生成樹的權重和
### 爛方法 : 窮舉
已知最小生成樹有 $n - 1$ 條邊，非樹邊有 $O(m)$ 條。若是窮舉兩者，我們就可以找出最小的差值。已知每條非樹邊都是由樹上兩個節點組成，在樹上也一定有路徑可以通往彼此。為了要保證圖是連通的，我們必須先窮舉非樹邊，邊上兩節點找到對應的樹上路徑來走訪，並拔掉樹上路徑最大邊權的邊。時間複雜度 $O(nm)$
<center>
<img src="https://hackmd.io/_uploads/SJ7weMj_xx.png" style="margin: 0 auto; display: block; width: 600px">
</center>
### 簡化生成樹上的搜尋
我們知道，若使用倍增法可以簡化兩點之間的詢問，是個很好的方法。可以考慮建立在此基礎上，用倍增法的方式維護「每個節點到 $2^i$ 代祖先的邊權最大值」
為了達成此目的，我們必須先建樹。我們直接在 Kruskal 演算法的片段插入 `g[]`，非樹邊的查詢也可以在這時候完成
```cpp
vector<Edge> notree;
for (int i = 0; i < m; i++) {
if (dsu.find(edge[i].u) != dsu.find(edge[i].v)) { // 如果兩點未聯通
dsu.merge(edge[i].u, edge[i].v); // 將兩點設成同一個集合
mst_val += edge[i].w; // 權重加進答案
g[edge[i].u].push_back({edge[i].v, edge[i].w});
g[edge[i].v].push_back({edge[i].u, edge[i].w});
}
else{
notree.push_back(edge[i]);
}
}
```
做好之後，我們可以開始建立生成樹了。這邊我們再多維護一個陣列 `mxcost[]` 維護「每個節點到 $2^i$ 代祖先的邊權最大值」
```cpp
void dfs_dep(int u, int pre) {
anc[u][0] = pre;
for (auto [v, w] : g[u]) {
if (v == pre) continue;
mxcost[v][0] = w; // 這裡紀錄一條邊的權重
dep[v] = dep[u] + 1;
dfs_dep(v, u);
}
}
void init() {
dfs_dep(1, 0);
for (int i = 1; i < logN; i++) {
for (int u = 1; u <= n; u++){
anc[u][i] = anc[anc[u][i - 1]][i - 1];
mxcost[u][i] = max(mxcost[u][i - 1], mxcost[anc[u][i - 1]][i - 1]);
}
}
}
```
最後在查詢的時候使用 `ret` 紀錄答案
```cpp
int getlca_val(int u, int v){ // 這邊用方法二來實作
if(dep[u] < dep[v]) swap(u, v);
ll ret = 0;
int k = dep[u] - dep[v];
for (int i = 0; i < logN; i++) {
if (k & (1 << i)){
ret = max(ret, mxcost[u][i]);
u = anc[u][i];
}
}
if(u == v) return ret;
for(int i = logN; i >= 0; i--){
if(anc[u][i] != anc[v][i]){
ret = max({ret, mxcost[u][i], mxcost[v][i]});
u = anc[u][i];
v = anc[v][i];
}
}
ret = max({ret, mxcost[u][0], mxcost[v][0]});
return ret;
}
```
### 查詢次小生成樹權重
最後在窮舉非樹邊的時候，直接加加減減就好了
```cpp
ll sbmst = INF;
for(int i = 0; i < notree.size(); i++){
int lca_val = getlca_val(notree[i].u, notree[i].v);
sbmst = min(sbmst, mst_val + notree[i].w - lca_val);
}
cout << sbmst << '\n';
```
如此一來就能求出次小生成樹的權重和囉!!
## 可能採雷的點
因為筆記也不可能涵蓋所有狀況，所以出問題的時候別怪我。大多 $\text{LCA}$ 會出的問題都放下面
### 實作上
- `logN` 沒定好，導致 **<font color="EEFF23">RE</font>**。建議可以將 `anc[][]` 陣列開大一點
- 倍增法爬到超過根節點 : 可能要加個 `if (anc[u][i])` 作為防護
- 根是 $0$ 還是 $1$ 還是其他? 這些實作細節沒注意到可能都會 **<font color="EEFF23">RE</font>**
- 有時候題目可能會是森林，會有多個根，需要注意一下
### 解題上
有時會誤以為 $\text{LCA}$、倍增法與時間戳記可以解決，但實際上測試時卻覺得行不通。這時你可以嘗試重心剖分、輕重樹鏈剖分或是嘗試引入 RMQ 技巧
### 溝通上
跟非競程人士溝通時，一定要跟別人說清楚你的 $\text{LCA}$ 是指「最低共同祖先」，不然別人會以為你的肚子不舒服
<center>
<img src="https://hackmd.io/_uploads/Ski9_PF_le.jpg" style="margin: 0 auto; display: block; width: 600px">
</center>
## 題目練習
[AtCoder Beginner Contest 138D - Ki](https://atcoder.jp/contests/abc138/tasks/abc138_d) (樹上前綴和裸題)
[AtCoder Beginner Contest 209D. Collision](https://atcoder.jp/contests/abc209/tasks/abc209_d) (樹上任意兩節點距離裸題)
[Zerojudge d767. 血緣關係](https://zerojudge.tw/ShowProblem?problemid=d767) (樹上任意兩節點距離裸題)
[CSES Company Queries II](https://cses.fi/problemset/task/1688/) (求 LCA 裸題)
[CSES Distance Queries](https://cses.fi/problemset/task/1135/) (樹上任意兩節點距離裸題)
[CSES Counting Paths](https://cses.fi/problemset/task/1136/) (樹上差分裸題)
[Codeforces 208E. Blood Cousins](https://codeforces.com/contest/208/problem/E) (動動腦，請善用時間戳記與一些 STL，不用找 LCA)
[Codeforces 609E. Minimum spanning tree for each edge](https://codeforces.com/problemset/problem/609/E) (次小生成樹半裸題)
[CSES MST Edge Check](https://cses.fi/problemset/task/3407) (應該跟上面一模一樣)
[Zerojudge c495. 四、次小生成樹(SBMST)](https://zerojudge.tw/ShowProblem?problemid=c495) (次小生成樹裸題，範測 2 有誤，應該是 37 38)
[Codeforeces 191C. Fools and Roads](https://codeforces.com/problemset/problem/191/C) (樹上「邊」差分，提示 : 改一點 `add()` 跟輸出的東西就好)
[Codeforeces 587C. Duff in the Army](https://codeforces.com/problemset/problem/587/C)
[AtCoder Beginner Contest 187E. Through Path](https://atcoder.jp/contests/abc187/tasks/abc187_e?lang=en) (前綴和)
[Codeforeces 519E. A and B and Lecture Rooms](https://codeforces.com/contest/519/problem/E) (動動腦)
[Codeforeces 178B3. Greedy Merchants](https://codeforces.com/contest/178/problem/B3)
[Codeforeces 466E. Information Graph](https://codeforces.com/contest/466/problem/E) (好像不是 LCA)
----
## 參考資料
- [海大競程 - Tree Algorithm 1](https://hackmd.io/@LeeShoWhaodian/2025Tree1#/)
- [Yui Huang 演算法學習筆記 - 【筆記】Lowest Common Ancestor 最近共同祖先](https://yuihuang.com/lowest-common-ancestor/)
- [Ian Shih - LCA (Lowest Common Ancestor / 最近共同祖先)](https://hackmd.io/@konchin/ryhgIlhMu)
- [台師大演算法筆記 - rooted tree](https://web.ntnu.edu.tw/~algo/RootedTree.html)
- [LCA problems](https://codeforces.com/blog/entry/43917)
- [OI Wiki - 前缀和 & 差分](https://oi-wiki.org/basic/prefix-sum/#%E6%A0%91%E4%B8%8A%E5%89%8D%E7%BC%80%E5%92%8C)
- [CP-Algorithms - Second Best Minimum Spanning Tree](https://cp-algorithms.com/graph/second_best_mst.html)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/8/17
Sign in with Wallet
Connect another wallet