# LCA

## 樹壓平
把Dfs時遍歷的節點的順序都記錄下來,就會產生一串字元,例如:

     A
   /  \
  B    E
 / \    \
C  D     F
dfs順序:ABCBDBAEFEA

這樣就叫做樹壓平,在dfs中順便紀錄每個節點的深度,再帶回dfs順序就會得到一串數字

dfs順序:ABCBDBAEFEA
depth  :01212101210

當我們要找lca(u,v)時,先找到dfs順序中最早出現的u的位置i,和dfs順序中最早出現的v的位置j,在區間[i,j]中找誰的depth有最小值,該點就是(u,v)的lca,例如:

     A
   /  \
  B    E
 / \    \
C  D     F

dfs順序:ABCBDBAEFEA
depth  :01212101210

(1)
假設要找lca(C,D):
區間:CBD
     212
1為最小值,所以1對應到的B就是lca(C,D);

(2)
假設要找lca(C,E):
區間:CBDBAE
     212101
0為最小值,所以0對應到的A就是lca(C,E);

那麼LCA問題就變成QRM問題了,可用[Segment Tree](/nrT8D7eqSUWZYrTEj3SjNQ),[Sparse Table](/jFKC0KV0S-6iQiPaao9Bcg)等資結來完成
:::spoiler ST Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define mem(a) memset(a,0,sizeof(a))
#define inf INT_MAX
#define mod 1000000007
#define MAXN 100005
int n,m,x,y,q,ans;
//-----------------------------------
vector<int> child[MAXN];
int fa[MAXN],node_idx[MAXN],node_depth[MAXN],idx;
pii st[MAXN][20];

void built(){
	for(int j=1;j<=log2(idx);j++){
		for(int i=0;i+(1<<j)-1<=idx;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}

pii query(int l,int r){
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}

void dfs(int now,int depth){
	node_depth[now]=depth;
	node_idx[now]=idx;
	
	st[idx][0].F=depth,st[idx++][0].S=now;
		
	for(auto i:child[now]){
		dfs(i,depth+1);
		st[idx][0].F=depth,st[idx++][0].S=now;		
	}
}

signed main(){
    cin.sync_with_stdio(0),cin.tie(0);
    cin >> n >> q;
		
	for(int i=1;i<=n;i++){
		while(cin >> x && x){
			child[i].pb(x);
			fa[x]++;
		}
	}
	
	for(int i=1;i<=n;i++){
		if(fa[i]==0){
			dfs(i,0);
			break;
		}
	}
	
	built();

	while(q--){
		cin >> x >> y;
		int lb=node_idx[x],rb=node_idx[y];
		if(lb>rb) swap(lb,rb);
	
		pii lca=query(lb,rb);
		int len=node_depth[x]-lca.F+node_depth[y]-lca.F;
		
		cout << lca.S << ' ' << len << '\n';
	}
}

:::

## 樹鏈剖分HDL
將一棵樹分成很多條鏈,也就是一串由上到下的結點,我們要找到一條主幹道(重鏈),其餘為次幹道,在每次查詢時,兩個點的top不在同一條鏈的話,就要把深度較低的top的節點往上跳到該節點的father,重複此步驟,直到兩點的top相同,接著深度較淺的點(較上面的點)就是LCA
:::spoiler HDL Code

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define MAXN 30005
int N=1,n,m,x,k,a,b,q,ans;
//-----------------------------------
int fa[MAXN],wson[MAXN],top[MAXN],depth[MAXN];
vector<int> Map[MAXN],sz(MAXN,1);

void dfs1(int now){
    for(auto i:Map[now]){
        fa[i]=now;  //record i's father
        depth[i]=depth[now]+1;  //record i's depth

        dfs1(i);

        sz[now]+=sz[i];  //record the number of subtree's node
        if(sz[i]>sz[wson[now]]) wson[now]=i;  //find the weight son
    }
}

void dfs2(int now,int tp){
	
    top[now]=tp;  //record the top
    if(wson[now]) dfs2(wson[now],tp);  //go to the weight son first

    for(auto i:Map[now]){
        if(i==wson[now]) continue;
        dfs2(i,i);  //go to the slight son second
    }
}

int query(int a,int b){
    while(top[a]!=top[b]){  //until a and b in the same chain
        if(depth[top[a]]>depth[top[b]]){  //take deeper top of element to its top's father
            a=fa[top[a]];
        }else{
            b=fa[top[b]];
        }
    }
    //return upper node,means the one has lower depth 
    if(depth[a]<depth[b]) return a;  
    else return b;
}


signed main(){
    cin.sync_with_stdio(0),cin.tie(0);
    
    cin >> n >> q;
    vector<bool> root(n+1,true);

    //input
    for(int i=1;i<=n;i++){	
        while(cin >> x && x){
            Map[i].pb(x);
            root[x]=false;
        }
    }

    //find the root
    int r=1;
    for(;r<=n;r++) if(root[r]) break;

    //built 
    dfs1(r);
    dfs2(r,r);

    //query
    while(q--){
        cin >> a >> b;
        int lca=query(a,b);
        cout << lca << ' ' << depth[a]+depth[b]-2*depth[lca] << '\n';
    }
}

:::