LCA的几种求法
1，st表 （最快~
int depth[maxn<<1],id[maxn],rid[maxn<<1],cnt,st[maxn<<1][25];
void dfs(int u,int fa,int d)
{
id[u]=++cnt;rid[cnt]=u;depth[cnt]=d;
for(int i=head[u];i;i=nxt[i]){
if(to[i]==fa)continue;
dfs(to[i],u,d+1);
rid[++cnt]=u;depth[cnt]=d;
}
}
int lg[maxn<<1];
void init()
{
lg[0]=-1;
for(int i=1;i<=cnt;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=cnt;i++)st[i][0]=i;
for(int j=1;(1<<j)<=cnt;j++)
for(int i=1;i+(1<<j)-1<=cnt;i++)
st[i][j]=depth[st[i][j-1]]<depth[st[i+(1<<j-1)][j-1]]?
st[i][j-1]:
st[i+(1<<j-1)][j-1];
}
int LCA(int u,int v)
{
if(id[u]>id[v])swap(u,v);
int s=id[u],t=id[v],len=lg[t-s+1];
return depth[st[s][len]]<depth[st[t-(1<<len)+1][len]]?rid[st[s][len]]:rid[st[t-(1<<len)+1][len]];
}
2，倍增
int dep[maxn],f[maxn][20];
void dfs(int u,int fa,int d)
{
dep[u]=d;f[u][0]=fa;
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa)dfs(to[i],u,d+1);
}
void init(int n)
{
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
if(f[i][j-1])f[i][j]=f[f[i][j-1]][j-1];
}
int LCA(int u,int v)
{
int i=0,j;
if(dep[u]<dep[v])swap(u,v);
for(i=1;(1<<i)<=dep[u];i++);i--;
for(j=i;j>=0;j--)
if(dep[u]-(1<<j)>=dep[v])u=f[u][j];
if(u==v)return u;
for(j=i;j>=0;j--)
if(f[u][j]!=-1&&f[u][j]!=f[v][j])
u=f[u][j],v=f[v][j];
return f[u][0];
}
下面这个代码简单点:
int din[maxn],dout[maxn],tnt,f[maxn][25];
void dfs(int u,int fa)
{
din[u]=++tnt;f[u][0]=fa;
for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa)dfs(to[i],u);
dout[u]=++tnt;
}
inline bool upper(int u,int v){
return din[u]<=din[v]&&dout[u]>=dout[v];
}
int LCA(int u,int v)
{
if(upper(u,v))return u;
for(int i=20;i>=0;i--)
if(!upper(f[u][i],v))u=f[u][i];
return f[u][0];
}
3，树剖
int siz[maxn],dep[maxn],fad[maxn],son[maxn],top[maxn],cnt;
void dfs1(int u,int fa,int d)
{
dep[u]=d;fad[u]=fa;siz[u]=1;son[u]=0;
for(int i=head[u];i;i=nxt[i])
{
if(to[i]==fa)continue;
dfs1(to[i],u,d+1);
siz[u]+=siz[to[i]];
if(siz[to[i]]>siz[son[u]])son[u]=to[i];
}
}
void dfs2(int u,int t)
{
top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=nxt[i])
if(to[i]!=son[u]&&to[i]!=fad[u])dfs2(to[i],to[i]);
}
int LCA(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fad[top[u]];
}
if(dep[u]>dep[v])return v;
return u;
}
4，LCT （可动态求LCA
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
//LCT
struct LCT{
int ch[maxn][2],f[maxn],tag[maxn],val[maxn],xs[maxn];
inline int getch(int x){return ch[f[x]][1]==x;}
inline int isroot(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;}
inline void pushdown(int p){
if(tag[p]){
if(ch[p][0])swap(ch[ch[p][0]][0],ch[ch[p][0]][1]),tag[ch[p][0]]^=1;
if(ch[p][1])swap(ch[ch[p][1]][0],ch[ch[p][1]][1]),tag[ch[p][1]]^=1;
tag[p]=0;
}
}
inline void pushup(int x){xs[x]=val[x]^xs[ch[x][0]]^xs[ch[x][1]];}
void update(int p){
if (!isroot(p))update(f[p]);
pushdown(p);
}
inline void rotate(int x){
int y=f[x],z=f[y],k=getch(x);
if (!isroot(y))ch[z][ch[z][1]==y]=x;
ch[y][k]=ch[x][!k],f[ch[x][!k]]=y;
ch[x][!k]=y,f[y]=x,f[x]=z;
pushup(x),pushup(y);
}
inline void splay(int x){
update(x);
for(int fa;fa=f[x],!isroot(x);rotate(x)){
if(!isroot(fa))rotate(getch(fa)==getch(x)?fa:x);
}
pushup(x);
}
inline int access(int x){
int p;
for(p=0;x;p=x,x=f[x]){
splay(x);ch[x][1]=p;pushup(x);
}
return p;
}
inline void makeroot(int p){
access(p);splay(p);
swap(ch[p][0],ch[p][1]);
tag[p]^=1;
}
inline void link(int x,int p){
if(find(x)==find(p))return;
makeroot(x);
splay(x);
f[x]=p;
}
inline void split(int x,int y){
makeroot(x);access(y);splay(y);
}
inline void cut(int x,int p){
split(x,p);
if(ch[p][0]==x&&!ch[x][1])ch[p][0]=f[x]=0;
}
inline int find(int p){
access(p);splay(p);
while(ch[p][0])p=ch[p][0];
splay(p);
return p;
}
inline int lca(int x,int y){access(x);return access(y);}
}st;
int main()
{
int n,m,s,u,v;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
st.link(u,v);
}
st.makeroot(s);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
printf("%d
",st.lca(u,v));
}
}