演算法學習筆記:最近公共祖先(LCA問題)

當我們處理樹上點與點關係的問題時(例如,最簡單的,樹上兩點的距離),常常需要獲知樹上兩點的最近公共祖先(Lowest Common Ancestor,LCA)。如下圖所示:

img

2號點是7號點和9號點的最近公共祖先

我們先來討論樸素的做法。

首先進行一趟dfs,求出每個點的深度:

int dep[MAXN];
bool vis[MAXN];
void dfs(int cur, int fath = 0)
{
    if (vis[cur])
        return;
    vis[cur] = true;
    dep[cur] = dep[fath] + 1; // 每個點的深度等於父節點的深度+1
    for (int eg = head[cur]; eg != 0; eg = edges[eg].next)
        dfs(edges[eg].to, cur);
}

現在A點的深度比B點深,所以我們先讓B點往上「爬」,爬到與A點深度相等為止。然後A點和B點再一起往上爬,直到兩點相遇,那一點即為LCA:

img

這樣下來,每次查詢LCA的最壞時間複雜度是 [公式] 的。


有時候,我們需要進行很多次查詢,這時樸素的 [公式] 複雜度就不夠用了。我們考慮空間換時間的倍增演算法。

倍增的思想直觀體現就在 ST表 中提及過。我們用一個數組fa[i][k]存儲 [公式] 號點的 [公式] 級祖先。(父節點為1級祖先,祖父結點為2級祖先……以此類推)

那麼這可以在dfs途中動態規劃得出:

// 在dfs中...
fa[cur][0] = fath;
for (int i = 1; i <= Log2[dep[cur]]; ++i) // Log2的預處理參見ST表的筆記
    fa[cur][i] = fa[fa[cur][i - 1]][i - 1]; // 這個DP也參見ST表的筆記

這樣,往上爬的次數可以被大大縮短(現在變成「跳」了)。

首先還是先讓兩點深度相等:

if (dep[a] > dep[b]) // 不妨設a的深度小於等於b
    swap(a, b);
while (dep[a] != dep[b]) // 跳到深度相等為止
    b = fa[b][Log2[dep[b] - dep[a]]]; // b不斷往上跳

例如,a和b本來相差22的深度,現在b不用往上爬22次,只需要依次跳16、4、2個單位,3次便能達到與a相同的距離。

兩者深度相等後,如果兩個點已經相遇,那麼問題就得以解決。如果尚未相遇,我們再讓它們一起往上跳。問題在於,如何確定每次要跳多少?正面解決也許不太容易,我們逆向思考:如何在a、b不相遇的情況下跳到儘可能高的位置?如果找到了這個位置,它的父親就是LCA了。

說來也簡單,從可能跳的最大步數Log2[dep[a]](這樣至多跳到0號點,不會越界)開始,不斷減半步數(不用多次循環):

for (int k = Log2[dep[a]]; k >= 0; k--)
    if (fa[a][k] != fa[b][k])
        a = fa[a][k], b = fa[b][k];

以剛剛那棵樹為例,先嘗試Log2[4]=2,A、B點的 [公式] 級祖先都是0(圖中未畫出),所以不跳。然後嘗試1,A、B的 [公式] 祖先都是2,也不跳。最後嘗試0,A、B的1級祖先分別是4和5,跳。結束。

img

這樣下來,再往上一格所得到的2號點就是所求的最近公共祖先。


主要程式碼如下:

int Log2[MAXN], fa[MAXN][20], dep[MAXN]; // fa的第二維大小不應小於log2(MAXN)
bool vis[MAXN];
void dfs(int cur, int fath = 0)
{
    if (vis[cur])
        return;
    vis[cur] = true;
    dep[cur] = dep[fath] + 1;
    fa[cur][0] = fath;
    for (int i = 1; i <= Log2[dep[cur]]; ++i)
        fa[cur][i] = fa[fa[cur][i - 1]][i - 1];
    for (int eg = head[cur]; eg != 0; eg = edges[eg].next)
        dfs(edges[eg].to, cur);
}
int lca(int a, int b)
{
    if (dep[a] > dep[b])
        swap(a, b);
    while (dep[a] != dep[b])
        b = fa[b][Log2[dep[b] - dep[a]]];
    if (a == b)
        return a;
    for (int k = Log2[dep[a]]; k >= 0; k--)
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}
int main()
{
    // ...
    for (int i = 2; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;
    // ...
    dfs(s); // 無根樹可以隨意選一點為根
    // ...
    return 0;
}

至於樹上兩點 [公式] 的距離,有公式 [公式] (很好推)。 [公式] 預處理, [公式] 查詢,空間複雜度為 [公式]

當然,以上都是針對無權樹的,如果有權值,可以額外記錄一下每個點到根的距離,然後用幾乎相同的公式求出。