AcWing 1172 祖孫詢問

題目描述：

給定一棵包含 n 個節點的有根無向樹，節點編号互不相同，但不一定是 1∼n。

有 m 個詢問，每個詢問給出了一對節點的編号 x 和 y，詢問 x 與 y 的祖孫關系。

輸入格式

輸入第一行包括一個整數 表示節點個數；

接下來 n 行每行一對整數 a 和 b，表示 a 和 b 之間有一條無向邊。如果 b 是 −1，那麼 a 就是樹的根；

第 n+2 行是一個整數 m 表示詢問個數；

接下來 m 行，每行兩個不同的正整數 x 和 y，表示一個詢問。

輸出格式

對于每一個詢問，若 x 是 y 的祖先則輸出 1，若 y 是 x 的祖先則輸出 2，否則輸出 0。

資料範圍

1≤n,m≤4×10^4,

1≤每個節點的編号≤4×10^4

輸入樣例：

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
           

輸出樣例：

1
0
0
0
2           

分析：

從這題開始就進入到最近公共祖先（Lowest Common Ancestors）的問題了。對于一棵有根樹，一個節點到根結點路徑上所有的節點都被稱為這個節點的祖先節點，祖先節點中除節點自身外的節點也被稱為真祖先節點。對于樹上的兩個不同節點u和v，其祖先節點必然有一些是重合的，其中深度最大的節點被稱為這兩個節點的最近公共祖先。

比如上圖中的D點和G點的最近公共祖先節點就是B點。首先介紹求解LCA問題的兩種基本方法：向上标記法和樹上倍增法。

向上标記法

我們自己是如何判斷LCA的呢？兩隻眼睛同時從D點和G點往上追溯，很快就可以定位到B點。計算機向上回溯自然不是問題，但是并不能很快的判斷出回溯過程中最先相交于哪一點，是以隻能異步的執行節點的回溯。首先D向上追溯到B點、A點，做好通路标記；然後G點向上追溯到E點，再往上到B點發現已經做好标記了，于是B點就是LCA節點。這種求解LCA的辦法被稱為向上标記法，由其中一個節點向上走到根節點并做好标記，另一個節點再往上走的時候第一次遇見的已标記的節點就是最近公共祖先節點。向上标記法過程相當簡單，書上說其複雜度是O（n），即正比于樹上節點的規模。其實該算法的複雜度用O（h），也就是樹高來衡量更加準确。

樹上倍增法

初學樹上倍增法的時候可能有些不了解，書中就是給出一個複雜的步驟然後告訴你這樣可以求出LCA，這些步驟是怎麼來的，為什麼需要這種算法，都沒有告訴我們。向上标記法看似簡單高效，因為隻需要O（h）的時間就可以求出LCA了，這個複雜度在樹的算法中已經是非常高效的了。我們求上圖中D和G的LCA固然很快，但是如果要求多對節點的LCA呢？比如求D、E的，求G、H的，...，我們會發現G點向上走的時候标記了其祖先節點，然後E向上走又會标記一遍祖先節點，向上回溯的路徑大都是相同的，這就存在很大的備援了，這種備援的來源正是向上标記法異步的特性，如果我們同步的向上回溯會怎樣呢？預處理下每個節點向上回溯任意步後的位置，記錄下來，然後用某種算法快速的求出兩個節點的LCA。最先遇見的困難就是節點u和節點v離他們的LCA節點的深度差不同，如果兩個節點處于同一深度，比如G和H點，深度都是3，我們完全可以二分答案了，先判斷下G和H向上兩步是不是到達了同一個節點，如果沒到達，就向上三步。如果兩個節點是處于同一深度的，我們在預處理節點向上走若幹步的資訊後，就可以在O（logh）的時間内求出LCA了。當然既可以使用二分求解也可以使用倍增求解，兩個節點同時向上走1,2,4，...步判斷是否到達了同一點。那麼我們在後面為什麼要選擇倍增而不是二分呢？這又是個問題。到這裡我們其實已經不知不覺的了解了樹上倍增法的第一個重要的步驟，将兩個節點調整到同一深度上。比如求u和v的LCA，u的深度是10，v的深度是6，首先求出u向上回溯到深度為6的祖先節點u1，如果u1就是v點，那麼LCA就是v，否則繼續求u1和v的LCA。此時就是求處于同一深度的兩個節點的LCA了，就十分友善了。是以樹上倍增法無非就是先将深度大的節點調整到與深度小的節點同一深度（向上回溯），然後繼續求LCA。

再回到開頭說的預處理出所有節點向上回溯若幹步的節點，但是這是十分沒有必要的。我們隻需要預處理出節點向上回溯2的倍數步的節點就可以滿足我們所有的需要了。比如要回溯11步，完全可以先走8步，再走2步，再走1步，任何十進制整數肯定是可以轉化為二進制表達的，11 = （1011），二進制拆分的思想足以讓我們走到任意的地方。為什麼是先走步數最大的再逐漸縮小步數，而不是先1再2再8呢？因為二進制拆分實作過程中并不需要我們真的去拆分11，我們可以先嘗試邁出一個很大的步數，比如16，發現比11大，于是邁出8步，再嘗試邁出4步，發現又超過11了，于是邁出2步，最後邁出1步，這是個不斷嘗試便于實作的倍增過程。調整到同一深度的兩個節點需要再次使用倍增的方法求LCA，比如先判斷下兩個節點向上回溯8步的節點是不是同一個，是就說明LCA不會在更高的位置了，于是重新判斷向上回溯4步的是不是同一個，如果不是，則說明LCA還在上面，再對這個邁出4步的兩個節點繼續向上回溯2步，直至兩個節點的父節點就是LCA為止。

下面用算法實作這一過程。設f[i][k]表示節點i向上回溯2^k步的節點标号，邊界情況f[i][0]表示i的父節點。f數組的求解就是使用倍增法常用的動态規劃公式了，或者叫分而治之，要想求出i向上走2^k步的節點，隻需要先求出i向上走2^(k-1)步的節點j，然後再求j向上走2^(k-1)步的節點即可。用狀态轉移方程表示就是f[i][k] = f[f[i][k-1]][k-1]，後者更直覺點令j = f[i][k-1]，f[i][k] = f[j][k-1]，預處理f數組的過程可以在bfs周遊樹的過程中順便實作，同時還可以記錄下所有節點的深度depth。

void bfs(int t){
    memset(depth,0x3f,sizeof depth);
    depth[0]= 0,depth[t] = 1;
    int hh = 0,tt = 0;
    q[0] = t;
    while(hh <= tt){
        int u = q[hh++];
        for(int i = h[u];~i;i = ne[i]){
            int j = e[i];
            if(depth[j] > depth[u] + 1){
                depth[j] = depth[u] + 1;
                q[++tt] = j;
                f[j][0] = u;
                for(int k = 1;k <= 15;k++){
                    f[j][k] = f[f[j][k - 1]][k - 1];
                }
            }
        }
    }
}           

初始情況下将所有節點的深度設定為無窮大，是以一旦從u可以走到j并且j的深度比u的深度+1還要大時，就說明u是j的父節點，同時可以更新j的深度了。我們知道bfs周遊樹的過程是層序周遊，周遊到j時j的祖先節點的資訊都已經被預處理過了，是以此時f[j][k] = f[f[j][k - 1]][k - 1];中的f[j][k-1]一定已經求出來了。

再來看下倍增的代碼：

int lca(int a,int b){
    if(depth[a] < depth[b]) swap(a,b);
    for(int k = 15;k >= 0;k--){
        if(depth[f[a][k]] >= depth[b])  a = f[a][k];
    }
    if(a == b)  return a;
    for(int k = 15;k >= 0;k--){
        if(f[a][k] != f[b][k]){
            a = f[a][k];
            b = f[b][k];
        }
    }
    return f[a][0];
}           

如果a深度大于b，就交換a、b節點 ，進而保持a節點一直在下面。然後就是按照上面所說的倍增的操作二進制拆分調整b到與a同一深度，如果兩點重合，LCA就是a點。否則，繼續對a、b向上倍增求LCA，最後的結果為什麼是a的父節點呢？這是因為倍增的終點就是a和b調整到LCA節點的下一層。舉個例子，比如a和b離LCA有6步，首先a和b都向上走4步，然後想向上走2步發現此時兩點重合了，于是隻走一步，此時倍增終止，a和b離LCA恰好是一步之遙。總的代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 40005,M = 80005;
int n,idx,h[N],e[M],ne[M];
int depth[N],q[N],f[N][16];
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void bfs(int t){
    memset(depth,0x3f,sizeof depth);
    depth[0]= 0,depth[t] = 1;
    int hh = 0,tt = 0;
    q[0] = t;
    while(hh <= tt){
        int u = q[hh++];
        for(int i = h[u];~i;i = ne[i]){
            int j = e[i];
            if(depth[j] > depth[u] + 1){
                depth[j] = depth[u] + 1;
                q[++tt] = j;
                f[j][0] = u;
                for(int k = 1;k <= 15;k++){
                    f[j][k] = f[f[j][k - 1]][k - 1];
                }
            }
        }
    }
}
int lca(int a,int b){
    if(depth[a] < depth[b]) swap(a,b);
    for(int k = 15;k >= 0;k--){
        if(depth[f[a][k]] >= depth[b])  a = f[a][k];
    }
    if(a == b)  return a;
    for(int k = 15;k >= 0;k--){
        if(f[a][k] != f[b][k]){
            a = f[a][k];
            b = f[b][k];
        }
    }
    return f[a][0];
}
int main(){
    scanf("%d",&n);
    int a,b,m,root;
    memset(h,-1,sizeof h);
    for(int i = 0;i < n;i++){
        scanf("%d%d",&a,&b);
        if(b == -1) root = a;
        else{
            add(a,b),add(b,a);
        }
    }
    bfs(root);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&a,&b);
        int p = lca(a,b);
        if(p == a)  puts("1");
        else if(p == b) puts("2");
        else    puts("0");
    }
    return 0;
}