关于树论【LCA树上倍增算法】

补了一发LCA，表示这东西表面上好像简单，但是细节真挺多。

我学的是树上倍增，倍增思想很有趣~~（爸爸的爸爸叫奶奶.偶不，爷爷）有一个跟st表非常类似的东西，f[i][j]表示j的第2^i的祖先，就是说f[0][x]是父亲，f[1][x]是爷爷，f[2][x]是高祖父(爷爷的爷爷)，f[3][x]是远祖父(高祖父的高祖父)

搞个事：

按古制辈份分为：自己，父亲、祖父、曾祖、高祖、天祖、烈祖、太祖、远祖、鼻祖。

扯回来，这个就是倍增的思想，可以方便的实现O(logn)的LCA，现在让你在构图的时候搞好f数组，一点问题都没有了吧~

然后怎么求LCA？首先，我们先让深度比较深的点往上跳，然后两个一起跳，直到跳到父亲相同。那我们跳的时候，就像二进制一样，可以一次跳2^i次方

caioj1236：（赤裸裸的LCA）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int x,y,next;
}a[210000];int len,last[110000];
void ins(int x,int y)
{
    a[++len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}
//f[i][j]表示j的第2^i的祖先
int Bin[30],dep[110000],f[25][110000];
void dfs(int x,int fa)//构树 
{
    f[0][x]=fa;//x的2^0=1就是自己父亲 
    for(int i=1;Bin[i]<=dep[x];i++)f[i][x]=f[i-1][f[i-1][x]];//倍增，爸爸的爸爸是爷爷 
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa)
        {
            dep[y]=dep[x]+1;
            dfs(y,x);
        }
    }
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);//让比较深的先往上跳 
    for(int i=20;i>=0;i--)//倒着，想象成二进制，比如要找第5个祖先，就变成101，从左往右把所有为一的跳一下 
        if(dep[x]-dep[y]>=Bin[i])x=f[i][x];
    if(x==y)return x;
    for(int i=20;i>=0;i--)//深度一样了，x和y一起跳
        if(dep[x]>=Bin[i]&&f[i][x]!=f[i][y]){x=f[i][x];y=f[i][y];}
    return f[0][x];
}
int main()
{
    Bin[0]=1;for(int i=1;i<=25;i++)Bin[i]=Bin[i-1]*2;
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    len=0;memset(last,0,sizeof(last));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    dep[1]=1;dfs(1,0);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}

关于树论【LCA树上倍增算法】

推荐阅读