挑战 LCA 学习以及个人理解

因为学的比较浅，直接上模板，有不足的地方请指正·-·！

既然要学LCA，那我们要明白LCA,是怎么定义的，怎么确定哪个是LCA。 LCA 被称为最近公共祖先。下面只介绍一种方法——倍增法【我不会说我只学了一种的】。

先写个大致的思路：接下来是按照这样的思路放模板。首先脑海里浮想出一棵树，然后节点u,v。OK ，可以开始放模板了。这题输入针对，可以一边看那题一边看模板，可能会好理解一点传送门！

for(int i=2;i<=n;i++) //G是一个滚动数组vector <int> G[maxn];这里的i只针对文章分类LCA中的第一篇。这段代码的要求是建树（也就是浮想出一棵树的实现）
    {
        int t;
        scanf("%d",&t);
        G[i].push_back(t);// 建立两个节点，无向图的关系。其实就是儿子和父亲的关系。
        G[t].push_back(i);
    }

建完图，开始对图进行初始化处理。处理出各点的深度。

void dfs(int v,int p,int d)//par[i][j]代表第j个点，向上走2^i次对应的节点
{
    par[0][v]=p;
    dep[v]=d;
    for(int i=0;i<G[v].size();i++)
        if(G[v][i]!=p)  dfs(G[v][i],v,d+1); // G[v][i]!=p是为了防止回溯。
    return ;
}
void init()
{
    dfs(root,-1,0);// dfs跑一遍图，处理深度
    for(int k=0;k<maxlog;k++) //   maxlog=ceil(log2(n))  n代表节点数，原因的话可以画一下图就可以知道是为什么了
        for(int v=1;v<=n;v++) // 枚举所有的节点1-n
            par[k+1][v]= par[k][v]<0 ? -1:par[k][par[k][v]];

对于顶点v ， 向上走两步的节点是par[par[v]].走4步的节点是par2[par[2]]。因此，向上走2^k次对应的顶点就是par[k][v].
<0的情况就是根节点往上走，因为走不上去，所有都是-1。
    return ;
}

接下来有上面关于点的深度，以及点走2^k步会走到哪个节点的信息。我们可以求LCA了。

int lca(int u,int v)
{
    if(dep[u]>dep[v])   swap(u,v); // 使得v是深度最大的节点。
    for(int k=0;k<maxlog;k++) // 目的是让u,v的深度相同。原因：相同了之后，再往上找第一个公共的点，那就是LCA了。
        if((dep[v]-dep[u])>>k & 1) // 意思是  delta(dep)/(2^k)后的值 mod2 。如果为1，那么要往上走2^k次步；否则不动。
            v=par[k][v];
    if(u==v)    return u;// 这里是为了防止同一条线两点重合的情况。如果不特判的话，return 的就是u的father了。结果就会出错
    for(int k=maxlog-1;k>=0;k--)
        if(par[k][u]!=par[k][v])    u=par[k][u],v=par[k][v];
    return par[0][u];
}

好了，这就是所有的模板了。
现在碰到LCA的题仅有一题：模型是，求两个点到确定点的最短路的公共点有多少个