---
tags: 109_FDCS
---
# LCA (Lowest Common Ancestor / 最近共同祖先)
## 何謂LCA
在一個有根樹(或DAG)上，同時擁有 $u, v$ 兩個點作為後代的點即為 $u, v$ 兩點的 $LCA$
i.e.
另外要注意，一個點本身也是自己的祖先
所以 $LCA(x,v)=x$
---
## 如何求LCA
隨便都可以想到 $O(n)$ 的作法，只要DFS過去就好
其中一個可行的算法如下，假設我們要對 $u, v$ 做LCA
可以對其中一個點，先假設是 $u$
一直往上找，直到 $u'$ 成為 $v$ 的祖先
i.e.
黃色框代表是 $v$ 的祖先，紅色則是往上找的的路徑
```cpp=
int LCA(int u, int v) {
if(isanc(u, v)) return u;
if(isanc(v, u)) return v;
while(!isanc(u, v))
u = anc[u];
return u;
}
```
其中`isanc`是用來判斷第一個引數是否為第二個引數的祖先
`anc`則是用來儲存每個點的父節點
`anc`很直覺，DFS就有了
`isanc`則需要借助另外兩個陣列`tin`和`tout`來實現
i.e.
```cpp=
bool isanc(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
```
`tin`和`tout`分別表示DFS進入及離開的時間點
從這張圖可以發現，一個子樹的根節點`tin`的值都會小於子節點`tin`的值
根節點`tout`的值都會大於子節點`tout`的值
所以只要有每個點`tin`和`tout`的值就可以判斷兩個點是否為對方的祖先
預處理具體實現如下
```cpp=
void build(int cur, int pre) {
static int t = 0;
anc[cur] = pre;
tin[cur] = t++;
for(const auto& i : edge[cur])
if(i.b != pre)
build(i.b, cur);
tout[cur] = t++;
}
```
由於一次往上找一格，所以這個演算法的時間複雜度為 $O(n)$
但很可惜有 <ruby>$O(logn)$<rt>更快的</rt></ruby> 作法，所以題目不會簡單的放過你
所以接下來就要介紹倍增法
---
## 倍增法
其實不難看出來，上面那種 $O(n)$ 的作法已經很接近 $O(logn)$ 的作法了
與上面方法不同的點在於，往上找祖先時，一次多往上找幾個
i.e.
乍看之下紅線好像毫無邏輯，但數一下可以發現
這些線都是往上 $2$ 的倍數父節點
觀察 $u$ 的祖先
i.e.
可以發現節點 $2$ 以上的點都是 $v$ 的祖先
節點 $5$ 以下都不是，很明顯，這符合進行二分搜所需的單調性
有很多方法可以實作這個二分搜，這裡使用實作起來相對簡單的方法
也就是找到不是 $v$ 的祖先的最高的節點，之後再回傳父節點就是LCA
已知根節點一定是 $u, v$ 的祖先，所以最差情況需要往上走 $n-1$ 步
這代表我們可以用小於 $n$ 以內的 $2$ 的冪次來組成 $n$ 以內的任何步數
以上面的圖來舉例，先往上找 $4$ 倍祖先，也就是節點 $1$
節點 $1$ 已經是 $v$ 的祖先，所以不更新 $u$
接下來往上找 $2$ 倍祖先的節點 $5$
節點 $5$ 不是 $v$ 的祖先，所以將 $u$ 更新成節點 $5$的位置
再來往上找 $1$ 倍祖先，節點 $2$
節點 $2$ 已經是 $v$ 的祖先，所以不更新 $u$
最後回傳 $u$ 所在位置 $5$ 的父節點，也就是 $2$
節點 $2$ 即是 $u, v$ 的LCA
### 預處理
對於每個節點，求出 $2^0,2^1,2^2...2^{logn}$ 倍的祖先
可以透過一個DFS來完成
一開始先將所有節點的所有倍祖先都先設成根節點
```cpp=1
V<V<int>> anc(n, V<int>(__lg(n)));
V<int> tin(n), tout(n);
```
之後做DFS，引數為當前節點和當前節點的父節點，並記錄`tin`和`tout`的時間點
```cpp=3
F<void(int, int)> build = [&](int cur, int pre) {
static int t = 0;
tin[cur] = t++;
//some operations
for (const auto& i : v[cur])
if (i != pre)
build(i, cur);
tout[cur] = t++;
};
```
在每個節點我們可以透過已經更新過的節點來更新當前節點的祖先
i.e.
當前節點的 $2^1$ 倍祖先就是 $2^0$ 倍祖先的 $2^0$ 倍祖先
而當DFS到當前節點時，代表祖先都已經DFS過了
code如下
```cpp=6
int k = pre;
for (int i = 0; i <= __lg(n); i++)
anc[cur][i] = k, k = anc[k][i];
```
將上面的code合起來，`build`函式如下
```cpp=
F<void(int, int)> build = [&](int cur, int pre) {
static int t = 0;
tin[cur] = t++;
int k = pre;
for (int i = 0; i <= __lg(n); i++)
anc[cur][i] = k, k = anc[k][i];
for (const auto& i : v[cur])
if (i != pre)
build(i, cur);
tout[cur] = t++;
};
```
### 查詢是否為祖先
利用`tin`和`tout`
上面提過，不贅述
```cpp=
auto isanc = [&](int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
};
```
### 查詢LCA
如果其中一個點為另一個點的祖先，則回傳
```cpp=
if (isanc(a, b)) return a;
if (isanc(b, a)) return b;
```
否則，利用二分搜往上找
原理上面也提過，多看兩次就會了
```cpp=3
for (int i = __lg(n); i >= 0; i--)
if (!isanc(anc[a][i], b))
a = anc[a][i];
```
最後，因為上面所求結果會是LCA的子節點
回傳時回傳父節點即為LCA
```cpp=6
return anc[a][0];
```
綜合起來就是查詢LCA的函式
```cpp=
auto lca = [&](int a, int b) {
if (isanc(a, b)) return a;
if (isanc(b, a)) return b;
for(int i = __lg(n); i >= 0; i--)
if (!isanc(anc[a][i], b))
a = anc[a][i];
return anc[a][0];
};
```
---
## 例題: [ZJ d767](https://zerojudge.tw/ShowProblem?problemid=d767)
### 題敘
給定一顆樹，根為節點 $1$
對每筆詢問求兩節點之 $LCA$ 及兩節點之間的距離
### 策略
$LCA$ 用倍增法就可求得
兩點間的距離可以多維護一個陣列 $d$ ，代表到根節點的距離
因為在樹上兩點之間只有一條路徑
代表該條路徑一定會通過 $LCA$
所以兩點間距離就是 $distance(u,LCA(u,v))+distance(v,LCA(u,v))$
而 $distance(u, LCA(u,v)) = d_u-d_{LCA(u,v)}$
$distance(v,LCA(u,v))$ 同理
最終得出
$distance(u,v)=d_u+d_v-2\times d_{LCA(u,v)}$
### code
```cpp=
template<typename T> using V = vector<T>;
template<typename T> using F = function<T>;
inline void solve() {
int n, q; cin >> n >> q;
V<V<int>> v(n), anc(n, V<int>(__lg(n) + 1));
V<int> in(n), out(n), d(n);
for (auto& i : v) {
static int ch;
while (cin >> ch, ch)
i.emplace_back(ch - 1);
}
F<void(int, int, int)> build = [&](int cur, int pre, int depth) {
static int t = 0;
in[cur] = t++;
d[cur] = depth;
for (int i = 0, k = pre; i <= __lg(n); i++)
anc[cur][i] = k, k = anc[k][i];
for (auto& i : v[cur])
if (i != pre)
build(i, cur, depth + 1);
out[cur] = t++;
};
auto isanc = [&](int a, int b) {
return in[a] <= in[b] && out[a] >= out[b];
};
auto query = [&](int a, int b) {
if (isanc(a, b)) return a;
if (isanc(b, a)) return b;
for (int i = __lg(n); i >= 0; i--)
if (!isanc(anc[a][i], b))
a = anc[a][i];
return anc[a][0];
};
build(0, 0, 0);
while (q--) {
static int a, b, tmp;
cin >> a >> b, a--, b--;
tmp = query(a, b);
cout << tmp + 1 << ' ' << d[a] + d[b] - 2 * d[tmp] << endl;
}
}
```
Sign in with Wallet
Connect another wallet