[TOC]

LCA，最近公共祖先

在有根树中，找出某两个结点u和v最近的公共祖先（或者说，离树根最远的公共祖先）。

问题模型

1 和 6 的 LCA 是 8 。
11 和 1 的 LCA 是 8 。
11 和 15 的 LCA 是 4 。
14 和 13 的 LCA 是 1 。

倍增

• 核心思想：分治
• 基本过程：
  1. 如果 a 和 b 深度不同，先把深度调浅，使他变得和浅的那个一样
  2. 现在已经保证了 a 和 b 的深度一样，所以我们只要把两个一起一步一步往上移动，直到他们到达同一个节点，也就是他们的最近公共祖先了。
• 优化：我们记一个节点的父节点为他的 倍祖先，他的父节点的父节点为他的 倍祖先，依此类推。
• 参考资料[ https://upload-images.jianshu.io/upload_images/13783432-25111ed2a25eac1a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240 ]

#include <iostream>
#include <cstring>
#include <cstdio> 
using namespace std;
const int MAX_N=100000;
const int MAX_M=1000000;
int isleave[100050];
struct edge{
    int v,next;
}E[MAX_M];
int p[MAX_N],eid;
void init(){
    memset(p,-1,sizeof(p));
    memset(isleave,0,sizeof(isleave));
    eid=0;
}
void insert(int u,int v){
    E[eid].v=v;
    E[eid].next=p[u];
    p[u]=eid++;
}
int d[MAX_N],fa[MAX_N][20];
void dfs(int u){
    for(int i=p[u];i!=-1;i=E[i].next){
        if(d[E[i].v]==-1){
            d[E[i].v]=d[u]+1;
            fa[E[i].v][0]=u;
            dfs(E[i].v);
        }
    }

}

int lca(int x,int y){
    int i,j;
    if(d[x]<d[y]){
        swap(x,y);
    }
    for(i=0;(1<<i)<=d[x];i++);
    i--;
    for(j=i;j>=0;j--){
        if(d[x]-(1<<j)>=d[y]){
            x=fa[x][j];
        }
    }
    if(x==y){
        return x;
    }
    for( j=i;j>=0;j--)
    {
        if(fa[x][j]!=fa[y][j]){
            x=fa[x][j];
            y=fa[y][j];
        }
    }
    return fa[x][0];
}
int main() {
    int n;
    init();
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        insert(u,v);
        insert(v,u);
        isleave[v]=1;
    }
    memset(d,-1,sizeof(d));
    int root;
    for(int i=1;i<=n;i++)
        {
        if(isleave[i]==0){
            root=i;
            break;
        }
    }
    d[root]=1;
    dfs(root);
    for(int level=1;(1<<level)<=n;level++){
        for(int i=1;i<=n;i++){
            fa[i][level]=fa[fa[i][level-1]][level-1];
        }
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    return 0;
}