什么是LCA

LCA（Lowest Common Ancestors）最近公共祖先

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u和v的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。

来看张图

图片说明

在这里，可以说5 6的最近公共祖先为2，同样的，3 8 的最近公共祖先为2
所以，在这里应该可以理解这个概念了

模板题：NKOJ最近公共祖先

题目

给出一棵有N(编号1到N)个节点的有根树，求出指定节点对的最近公共祖先！
对于树中节点x而言，从根节点到达x的这一条路径中经过的所有节点，都称为x的祖先。
如上图所表示的树中，根节点为8。8、4、10、16都是12的祖先。对于6和12这对节点而言，从6出发往上朝根走和从12出发往上朝根走的两条路径最早交汇的地点是4号节点，因此4号点是6和12的最近公共祖先。
同理，11和9的最近公共祖先是8; 10和3的最近公共祖先是10；2和7的最近公共祖先是4......

输入格式

第一行，一个整数N。表示树中节点总数
接下来N-1行，每行两个整数x和y,表示x是y的父亲。
接下来一行，一个整数M,表示询问的总数
接下来M行，每行两个整数a和b,表示询问a和b的最近公共祖先。

Input

16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
3
16 7
14 9
3 10

Output

4
8
10

题目思路

如果不用LCA，肯定是枚举走到黑了
可以看到，这道题所要求的操作正是LCA的功能，接下来具体看看LCA怎么实现

倍增法求LCA

初始化

首先我们定义两个数组

fa[][]数组：用来记录一棵树里面的父子关系
Dep[]数组：Dep[i]表示i层的深度

然后我们从根节点开始搜索更新fa数组：

 fa[v][k]=fa[fa[v][k-1]][k-1]

这个公式的含义我就不多赘述了，简洁明了

注意：这里的k为最大的不超过x的深度（Dep[x]）即满足2^k<=Dep[x]

初始化DFS代码实现

void DFS(int x){
    int k,y;
    Dep[x]=Dep[Fa[x][0]]+1;
    k=ceil(log2(Dep[x]));
    for(int i=1;i<=k;i++)Fa[x][i]=Fa[Fa[x][i-1]][i-1];
    int i=Last[x];
    while(i){
        //链式前向星的写法
        y=End[i];
        DFS(y);
        i=Next[i];
    }
}

向上走！

寻找最近公共祖先，必然要往树的根部（也就是上方）走，所以需要一个函数来实现向上走的操作
核心：

if(p&(1<<i)) v=fa[v][i]

模拟一下过程
图片说明
向上5层，p=5=(101)2

i=0, (p&(1<<i))==(101&1)2==1 , v=fa[v][0]
i=1, (p&(1<<i))==(101&10)2==0

i=2, (p&(1<<i))==(101&100)2==1 , v=fa[v][2]

向上走（伪代码）

Go_up(int v,int p) { 
   for(int i=0;i<S;i++)
      if(p&(1<<i)) v=fa[v][i];
}

LCA的实现

图片说明

首先，将两个元素移到同一层里

if(Dep[x]<Dep[y])swap(x,y);
 k=Dep[x]-Dep[y];
 for(int i=0;i<=s;i++){
     if(k&(1<<i))x=Fa[x][i];
}

注意：这里我没有用go_up函数而是直接进LCA

然后就是倍增操作，我们依次倍增，如果u，v的祖先不相同，就更新为新的那两个点，如果相同，那么也不一定是最近的公共祖先
```
if(x==y)return x;
 s=ceil(log2(Dep[x]));
 for(int i=s;i>=0;i--){
     if(Fa[x][i]!=Fa[y][i]){
         x=Fa[x][i];
         y=Fa[y][i];
     }
 }
 return Fa[x][0];
```

注意：如果出现了相等的情况，相当于为同一节点，直接返回

完整LCA

int LCA(int x,int y){
  int k,s;
  s=ceil(log2(n));
  if(Dep[x]<Dep[y])swap(x,y);
  k=Dep[x]-Dep[y];
  for(int i=0;i<=s;i++){
      if(k&(1<<i))x=Fa[x][i];
  }
  if(x==y)return x;
  s=ceil(log2(Dep[x]));
  for(int i=s;i>=0;i--){
      if(Fa[x][i]!=Fa[y][i]){
          x=Fa[x][i];
          y=Fa[y][i];
      }
  }
  return Fa[x][0];
}

开始的这道题

有了以上两个操作，这道题迎刃而解了
附上源代码

#include<iostream>
#include<bits/stdc++.h> 

using namespace std;

int End[10005],Fa[10005][10005],Next[10005],Last[10005];
int n,x,y,m;
int Dep[10005];

void DFS(int x){
    int k,y;
    Dep[x]=Dep[Fa[x][0]]+1;
    k=ceil(log2(Dep[x]));
    for(int i=1;i<=k;i++)Fa[x][i]=Fa[Fa[x][i-1]][i-1];
    int i=Last[x];
    while(i){
        y=End[i];
        DFS(y);
        i=Next[i];
    }
}

int LCA(int x,int y){
    int k,s;
    s=ceil(log2(n));
    if(Dep[x]<Dep[y])swap(x,y);
    k=Dep[x]-Dep[y];
    for(int i=0;i<=s;i++){
        if(k&(1<<i))x=Fa[x][i];
    }
    if(x==y)return x;
    s=ceil(log2(Dep[x]));
    for(int i=s;i>=0;i--){
        if(Fa[x][i]!=Fa[y][i]){
            x=Fa[x][i];
            y=Fa[y][i];
        }
    }
    return Fa[x][0];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&x,&y);
        Fa[y][0]=x;
        End[i]=y;
        Next[i]=Last[x];
        Last[x]=i;
    }
    for(int i=1;i<=n;i++){
        if(Fa[i][0]==0){
            DFS(i);
            break;
        }
    }
    cin>>m;
    while(m--){
        scanf("%d%d",&x,&y);
        cout<<LCA(x,y)<<endl;
    }
}

写在最后

如有错误，欢迎指出~~

倍增法求LCA基础模板[NKOJ最近公共祖先]