lca指的是树上两点的最近公共祖先，也就是说，在这两点的所有祖先中深度最大的就是它们的最近公共祖先。

求解lca的方法一般情况下有三种：向上标记法，树上倍增法，tarjan

此处只介绍前两种方法（因为不会tarjan）

---

 

• 向上标记法

　　　　假定一棵树有8个节点，如图所示， lca(4,7)=1

　　

　　　　  例如求4处有一只小兔子A，7处也有一只小兔子B，它们都只能顺着这棵树向上跳

　　　　现在想要知道它们最近可以在什么地方见面

　　　　解决这个问题，其实就是求lca（4，7）

　　　　我们让小兔子A从4向上跳到根节点，并标记所有经过的节点

　　　　同样的，让小兔子B从7向上走到根节点，第一次遇到的被标记的节点就是4和7的最近公共祖先

　　　　时间复杂度最坏为O（n）

　　下面重点介绍树上倍增法（因为常用）

• 树上倍增法

　　　　仍然是上图，求同样的问题

　　　　可以发现4的深度比7的深度深

　　　　那么让小兔子A从4向上跳，直到和小兔子B所在的节点7同一深度时停下来

　　　　此时如果两只小兔子已经会面，那么此时它们所在的点就是lca（4，7）的值

　　　　如果没有会面呢？

　　　　那么就让两只小兔子一起向上跳，直到它们会面为止

　　　　但是有一个问题，如果小兔子A所在的树链特别的长，那它岂不是要跳好久才能和小兔子B到同一高度？

　　　　所以聪明的小兔子就想出了一个办法：每次按2的i次幂跳

　　　　这就用到了倍增

　　　　这样子在数据最坏的情况下两只小兔子也可以很快见面啦

 

　　　　不妨设f[x][i]表示x向上的第2ⁱ个节点

　　　　对于初始化，显然f[x][0]也就表示x的父节点

　　　　对于范围内的任意i,f[x][i]=f[ f[x][i-1] ][i-1]

　　　　除了f数组之外，我们还需要一个d数组记录每个点的深度

　　　　具体如何求解lca（x，y）呢？步骤如下：

　　　　　　首先找出深度更深的点x（如果y比x深度深就交换)

　　　　　　然后让x向上倍增直到与y同一深度

　　　　　　如果此时x与y是同一点，那么就返回x所在位置（返回y所在位置也无所谓）

　　　　　　如果不是同一点就一起向上倍增，直到是同一点就返回此时点所在的位置

　　　　如果还是有疑问，那么就请参考以下程序理解吧

　　　　另外，我用的是vector存图，当然也可以用链式前向星

vector
     
       g[maxn];void pre(int u,int fa){
    //初始化     d[u]=d[fa]+1;//求深度     for(int i=1;i<=15;i++){
    //i的范围根据题的数据范围而定         f[u][i]=f[f[u][i-1]][i-1];    }    int sz=g[u].size();//表示u所连接的边数     for(int i=0;i
      
       =0;i--){
    //跳到同一深度         if(d[f[x][i]]>=d[y]){            x=f[x][i];        }        if(x==y){
    //如果此时是同一个点就输出             return x;        }    }    for(int i=15;i>=0;i--){
    //让x，y同时向上跳         if(d[f[x][i]]!=d[f[y][i]]){
    //如果不是同一点就更新x，y的值             x=f[x][i];             //如果是同一点那么x的父节点就是答案             y=f[y][i];        }    }    return f[x][0];//答案就是x的父节点 }
      
     

 

就这么多啦 欢迎指正