# lowest common ancestor

:::info
一個樹中，兩相異點的最低祖先（兩點都能連到而且距兩點最近的一點）
:::

eulerian tour+RMQ
--

* 先做一個euler tour (dfs)，從頭一路到底，左邊優先，回到根後在到下一個子節點，每次到達一個點都要紀錄高度
* 也要紀錄每個節點編號對應到height表中的位置（last表格），如果一個節點對應到多個位置（非葉節點都是），只須紀錄最後的位置，因為查詢時兩點最小值不會變


| index: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| ------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| height: | 1 | 2 | 3 | 2 | 3 | 2 | 1 | 2 | 1 | 2 | 3 | 2 | 1 |
| node: | 1 | 2 | 5 | 2 | 6 | 2 | 1 | 3 | 1 | 4 | 7 | 4 | 1 |

| index: | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ------- | ---- | --- | --- | --- | --- | --- | ---- |
| last: | 1 | 6 | 8 | 12 | 3 | 5 | 11 |

* 從last表中找出要找的兩個點x, y對應到height表的位置，並在兩個位置之間找height最小值（height值從上到下遞增）即所求，因為是在eulerian tour時兩點之間最高點，也是最低共同祖先
* $lca(x, y)=node[\ min\_element\_index(height[\ last[x]\sim\ last[y]\ ])\ ]$
* $min\_element\_index()$即為區間最小值的位置，用sparse table
* 預處理：$O(n+nlogn)$, 查詢：$O(1)$

https://zerojudge.tw/ShowProblem?problemid=d767

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

vector<int> g[30010], ht, node, log_2;
int last[30010];
vector<vector<LL>> sp;

void dfs(int depth, int e){
    for(auto a:g[e]){
        last[e]=ht.size();
        ht.EB(depth);
        node.EB(e);
        dfs(depth+1, a);
    }
    last[e]=ht.size();
    ht.EB(depth);
    node.EB(e);
}

LL query(int l, int r){
    int k=log_2[r-l+1];
    if(ht[sp[l][k]]>ht[sp[r-(1<<k)+1][k]]) return sp[r-(1<<k)+1][k];
    return sp[l][k];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL n, q, a, b;
    cin>>n>>q;
    rep(i,1,n+1){
        while(cin>>a){
            if(a==0) break;
            g[i].EB(a);
        }
    }

    //eulerian tour
    dfs(1, 1);

    //sparse table
    LL len=ht.size();
    log_2.resize(len+1);
    sp.resize(len+1, vector<LL>(30));
    log_2[1]=0;
    for(int i=2;i<=len;++i) log_2[i]=log_2[i/2]+1;
    rep(i,0,len) sp[i][0]=i;
    for(int j=1;j<=log_2[len];++j){
        for(int i=0;i+(1<<j)<=len;++i){
            if(ht[sp[i][j-1]]>ht[sp[i+(1<<(j-1))][j-1]]) sp[i][j]=sp[i+(1<<(j-1))][j-1];
            else sp[i][j]=sp[i][j-1];
        }
    }

    while(q--){
        cin>>a>>b;
        int pos=query(min(last[a], last[b]), max(last[a], last[b]));
        cout<<node[pos]<<" "<<ht[last[a]]-ht[pos]+ht[last[b]]-ht[pos]<<NL;
    }
}

倍增法
---

* [倍增法](/DFzViRxSTvGCBu38I8b2ig)

ll n, q, par[200010][21];
vector<int> adj[200010];
int level[200010];
 
void dfs(int v){
    for(auto a:adj[v]){
        par[a][0]=v;
        level[a]=level[v]+1;
        dfs(a);
    }
}
 
ll lca(int a, int b){
    if(level[a]<level[b]) swap(a, b);
    //set a and b to the same level
    int d=level[a]-level[b];
    rep(i,0,21) if(d & (1<<i)) a=par[a][i];
    if(a==b) return a;
    for(int i=20;i>=0;--i){
        if(par[a][i]!=par[b][i]){
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}
 
void solve(){
    cin>>n>>q;
    ll v;
    rep(i,2,n+1){
        cin>>v;
        adj[v].pb(i);
    }
    par[1][0]=1;
    level[1]=1;
    dfs(1);
    for(int j=1;j<=20;++j){
        for(int i=1;i<=n;++i){
            par[i][j]=par[par[i][j-1]][j-1];
        }
    }
    int a, b;
    while(q--){
        cin>>a>>b;
        cout<<lca(a, b)<<NL;
    }
}