ST表——【模板】最近公共祖先（LCA）

题目来源

洛谷P3379【模板】最近公共祖先（LCA）

https://daniu.luogu.org/problem/show?pid=3379

蒟蒻代码（C++)

#include <cmath>
#include <cstdio>
#include <bitset>
using namespace std;
bitset<500010> g;
int he[5000010],en[5000010],ne[5000010];
int f[5000010][20],fi[5000010];
int n,m,s,x,y,cnt=0,de[5000010],euler[5000010];
inline void add();
inline int read();
int lca(int x,int y);
void dfs(int pos,int depth);
int main()
{
    n=read(); m=read(); s=read();
    for(int i=1;i<n;++i)
        x=read(),y=read(),add();
    cnt=0;
    dfs(s,1);
    for(int i=1;i<=cnt;++i)
        f[i][0]=euler[i];
    for(int j=1;j<20;++j)
    {
        for(int i=1;i<=cnt;++i)
        {
            if(i+(1<<j)>cnt)
                break;
            if(de[f[i][j-1]]<de[f[i+(1<<(j-1))][j-1]])
                f[i][j]=f[i][j-1];
            else
                f[i][j]=f[i+(1<<(j-1))][j-1];
        }
    }
    for(int i=1;i<=m;++i)
    {
        x=read();    y=read();
        x=fi[x];    y=fi[y];
        if(x<=y)
            printf("%d\n",lca(x,y));
        else
            printf("%d\n",lca(y,x));
    }    
    return 0;
}
int lca(int x,int y)
{
	int p=int(log(y-x+1)/log(2));
    int res=f[x][p];
    int k=f[y-(1<<p)+1][p];
    if(de[res]>de[k])
    	res=k;
    return res;
}
inline int read()
{
    char x=getchar();    int num=0;
    while(!(x>=48&&x<=57))
        x=getchar();
    while(x>=48&&x<=57)
        num=num*10+x-48,x=getchar();
    return num;
}
void dfs(int pos,int depth)
{
    g[pos]=1;        de[pos]=depth;
    fi[pos]=++cnt;    euler[cnt]=pos;
    int k=he[pos];
    while(k)
    {
        if(g[en[k]]==0)
        {
            dfs(en[k],depth+1);
            euler[++cnt]=pos;
        }    
        k=ne[k];
    }
}
inline void add()
{
    ++cnt; en[cnt]=y; ne[cnt]=he[x]; he[x]=cnt;
    ++cnt; en[cnt]=x; ne[cnt]=he[y]; he[y]=cnt;
}