本文主要是介绍O(nlogn)~O(1)的LCA，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
RT，这个算法感觉超级有用
大概就是说搞出来欧拉序
（欧拉序就是每个点进入时记录一次，从每一个子树出来时记录一次）
然后再欧拉序上搞RMQ，就可以了，具体可以自己画个图看看
这东西超级好写的，常数又小
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=' ';while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=1e6+5;
int n,m,s,tot,cnt;
int head[N],to[N],Next[N],Log[N];
inline void addedge(int x,int y){to[++tot]=y;Next[tot]=head[x];head[x]=tot;}
int a[N],dep[N],mn[21][N],p[N];
inline void dfs(int x,int fa){a[++cnt]=x;p[x]=cnt;dep[x]=dep[fa]+1;for(int i=head[x];i;i=Next[i]){int u=to[i];if(u==fa)continue;dfs(u,x);a[++cnt]=x;}
}
int main(){n=read();m=read();s=read();Log[0]=-1;for(int i=1;i<n;++i){int x=read(),y=read();addedge(x,y);addedge(y,x);}dfs(s,0);for(int i=1;i<=cnt;++i)mn[0][i]=a[i];for(int i=1;i<=20;++i)for(int j=1;j+(1<<i)<=cnt;++j)if(dep[mn[i-1][j]]<dep[mn[i-1][j+(1<<(i-1))]])mn[i][j]=mn[i-1][j];else mn[i][j]=mn[i-1][j+(1<<(i-1))];for(int i=1;i<=cnt;++i)Log[i]=Log[i>>1]+1;for(int i=1;i<=m;++i){int x=read(),y=read();if(p[x]>p[y])swap(x,y);int k=Log[p[y]-p[x]+1],ans;if(dep[mn[k][p[x]]]<dep[mn[k][p[y]-(1<<k)+1]])ans=mn[k][p[x]];else ans=mn[k][p[y]-(1<<k)+1];printf("%d\n",ans);}return 0;
}这篇关于O(nlogn)~O(1)的LCA的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
