struct LeastCommonAncestor
{
static const int __=10005;
static const int logn=15;
struct edge
{
int x,val;
edge(int x,int y):
x(x),val(y) {}
};
vector<edge>G[__];
int n,pre[__][logn],dis[__][logn],dep[__];
void add_edge(int x,int y,int z)
{
G[x].pb(edge(y,z));
}
void dfs(int x,int fa,int dist)
{
pre[x][0]=fa,dis[x][0]=dist,dep[x]=dep[fa]+1;
fup(i,0,sz(G[x])-1)
if(G[x][i].x!=fa)
dfs(G[x][i].x,x,G[x][i].val);
}
void init(int _n)
{
n=_n;
dfs(1,0,0);
fup(i,1,logn-1)
fup(j,1,n)
{
pre[j][i]=pre[pre[j][i-1]][i-1];
dis[j][i]=dis[j][i-1]+dis[pre[j][i-1]][i-1];
}
}
int get_lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
fdn(i,logn-1,0)
if(pre[x][i] && dep[pre[x][i]]>=dep[y])
x=pre[x][i];
if(x==y)return x;
fdn(i,logn-1,0)
if(pre[x][i]!=pre[y][i])
x=pre[x][i],y=pre[y][i];
return pre[x][0];
}
int get_dis(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
int sum=0;
fdn(i,logn-1,0)
if(pre[x][i] && dep[pre[x][i]]>=dep[y])
sum+=dis[x][i],x=pre[x][i];
if(x==y)return sum;
fdn(i,logn-1,0)
if(pre[x][i]!=pre[y][i])
sum+=dis[x][i]+dis[y][i],x=pre[x][i],y=pre[y][i];
sum+=dis[x][0]+dis[y][0];
return sum;
}
int get_kth(int x,int y,int k)
{
int lca=get_lca(x,y);
if(k==dep[x]-dep[lca]+1)return lca;
if(k<dep[x]-dep[lca]+1)
{
k--;
fdn(i,logn-1,0)
if(pre[x][i] && k>=(1<<i))
k-=(1<<i),x=pre[x][i];
return x;
}
if(k>dep[x]-dep[lca]+1)
{
k=dep[x]+dep[y]-2*dep[lca]-k+1;
fdn(i,logn-1,0)
if(pre[y][i] && k>=(1<<i))
k-=(1<<i),y=pre[y][i];
return y;
}
}
void clear(){fup(i,1,n)G[i].clear();}
}lca;
树链剖分:
struct bian
{
int nex,nex_node;
bian(int nex=0,int nex_node=0):
nex(nex),nex_node(nex_node) {}
} edge[1000005];
int head[500005],edge_num=0;
void add_edge(int now,int nex)
{
edge[edge_num]=bian(nex,head[now]);
head[now]=edge_num++;
}
int pre[500005],dep[500005];
int top[500005],heavy[500005];
int dfs(int x,int fa,int depth)
{
dep[x]=depth,pre[x]=fa;
int res=1,maxx=0;
for(int i=head[x]; ~i; i=edge[i].nex_node)
{
int nex=edge[i].nex;
if(nex==fa)continue;
int t=dfs(nex,x,depth+1);
if(t>maxx)maxx=t,heavy[x]=nex;
res+=t;
}
return res;
}
void slpf(int x,int fa,int tp)
{
top[x]=tp;
if(heavy[x])slpf(heavy[x],x,tp);
for(int i=head[x]; ~i; i=edge[i].nex_node)
{
int nex=edge[i].nex;
if(nex==fa)continue;
if(nex!=heavy[x])slpf(nex,x,nex);
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
if(dep[top[x]]>dep[top[y]])
x=pre[top[x]];
else y=pre[top[y]];
if(dep[x]>dep[y])swap(x,y);
return x;
}
int main()
{
memset(head,-1,sizeof(head));
int n,q,root,x,y;
scanf("%d%d%d",&n,&q,&root);
for(int i=1; i<=n-1; i++)
{
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
dfs(root,0,1);
slpf(root,0,root);
while(q--)
{
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
Tarjan(离线)算法:
原创模板:
int n;
vector<int>G[10005];
int pre[10005];
int vis[10005];
int alr[10005];
void init(int x)
{
for(int i=1; i<=x; i++)
pre[i]=i;
}
int a,b;
int find(int x)
{
if(pre[x]==x)return x;
else return find(pre[x]);
}
int flag=0;
void dfs(int x,int fa)
{
if(flag)return;
int len=G[x].size();
for(int i=0; i<len; i++)
{
int next=G[x][i];
if(!alr[next])
{
alr[next]=1;
dfs(next,x);
if(flag)return;
alr[next]=0;
}
}
vis[x]=1;
if(x==a&&vis[b])flag=find(b);
if(x==b&&vis[a])flag=find(a);
pre[x]=fa;
}
int main()
{
int T,mk;
scanf("%d",&T);
while(T--)
{
flag=0;
memset(vis,0,sizeof(vis));
memset(alr,0,sizeof(alr));
scanf("%d",&n);
init(n);
for(int i=0; i<n-1; i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(i==0)mk=x;
G[x].push_back(y);
G[y].push_back(x);
}
scanf("%d%d",&a,&b);
alr[mk]=1;
dfs(mk,mk);
printf("%d\n",flag);
for(int i=1; i<=n; i++)G[i].clear();
}
return 0;
}
RMQ-ST(在线)算法:
struct node
{
int val,id;
};
vector<int>G[500005];
int vis[500005];
int first[500005];
node minn[500005][21];
int cont=1;
void dfs(int node,int depth)
{
minn[cont][0].id=node;
if(!first[node])first[node]=cont;
minn[cont++][0].val=depth;
int len=G[node].size();
for(int i=0; i<len; i++)
if(!vis[G[node][i]])
{
vis[G[node][i]]=1;
dfs(G[node][i],depth+1);
vis[G[node][i]]=0;
minn[cont][0].id=node;
minn[cont++][0].val=depth;
}
}
void rmq(int n)
{
for(int j=1; (1<<j)<=n; j++)
for(int i=1; i+(1<<(j-1))<=n; i++)
if(minn[i][j-1].val<minn[i+(1<<(j-1))][j-1].val)
{
minn[i][j].val=minn[i][j-1].val;
minn[i][j].id=minn[i][j-1].id;
}
else
{
minn[i][j].val=minn[i+(1<<(j-1))][j-1].val;
minn[i][j].id=minn[i+(1<<(j-1))][j-1].id;
}
}
int findmin(int l,int r)
{
int k=0;
if(l>r)swap(l,r);
while((1<<(k+1))<=r-l+1)k++;
if(minn[l][k].val<minn[r-(1<<k)+1][k].val)
return minn[l][k].id;
else
return minn[r-(1<<k)+1][k].id;
}
int main()
{
int n,m,x,y,a,b,root;
scanf("%d%d%d",&n,&m,&root);
for(int i=0; i<n-1; i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
vis[root]=1;
dfs(root,1);
rmq(cont);
for(int i=0; i<m; i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",findmin(first[a],first[b]));
}
return 0;
}
在线:
struct node
{
int val,id;
};
map<string,int>mp1;
map<int,string>mp2;
vector<int>G[200005];
int deep[200005],order[200005],first[200005],pre[200005],cont;
bool vis[200005];
node minn[200005][20];
void dfs(int node,int depth)
{
vis[node]=true;
order[cont]=node;
if(!first[node])first[node]=cont;
deep[cont++]=depth;
int len=G[node].size();
for(int i=0; i<len; i++)
{
int next=G[node][i];
dfs(next,depth+1);
order[cont]=node;
deep[cont++]=depth;
}
}
void rmq(int n)
{
for(int j=1; (1<<j)<=n; j++)
for(int i=1; i+(1<<(j-1))<=n; i++)
if(minn[i][j-1].val<minn[i+(1<<(j-1))][j-1].val)
{
minn[i][j].val=minn[i][j-1].val;
minn[i][j].id=minn[i][j-1].id;
}
else
{
minn[i][j].val=minn[i+(1<<(j-1))][j-1].val;
minn[i][j].id=minn[i+(1<<(j-1))][j-1].id;
}
}
int findmin(int l,int r)
{
int k=0;
if(l>r)swap(l,r);
while((1<<(k+1))<=r-l+1)k++;
if(minn[l][k].val<minn[r-(1<<k)+1][k].val)
return minn[l][k].id;
else return minn[r-(1<<k)+1][k].id;
}
int find(int x)
{
if(pre[x]==x)return x;
else return find(pre[x]);
}
int main()
{
int n,k=1;
char a[50],b[50];
scanf("%d",&n);
for(int i=1;i<=100;i++)
pre[i]=i;
for(int i=0; i<n; i++)
{
scanf("%s%s",a,b);
if(!mp1[a])
{
mp1[a]=k;
mp2[k++]=a;
}
if(!mp1[b])
{
mp1[b]=k;
mp2[k++]=b;
}
G[mp1[a]].push_back(mp1[b]);
}
cont=1;
for(int i=1; i<k; i++)
if(!vis[find(i)])dfs(find(i),1);
for(int i=1; i<cont; i++)
{
minn[i][0].val=deep[i];
minn[i][0].id=order[i];
}
rmq(cont);
char x[50],y[50];
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",x,y);
cout<<mp2[findmin(first[mp1[x]],first[mp1[y]])]<<'\n';
}
return 0;
}
离线:
struct node
{
int nex,id;
} t;
int pre[100005];
int ans[100005];
bool vis[100005];
bool alr[100005];
char re[100005][50];
map<string,int>mp;
vector<int>G[100005];
vector<node>Que[100005];
int find(int x)
{
if(pre[x]==x)return x;
else
return pre[x]=find(pre[x]);
}
void dfs(int fa,int x)
{
int len=G[x].size();
for(int i=0; i<len; i++)
{
int nex=G[x][i];
if(!alr[nex])
{
alr[nex]=true;
dfs(x,nex);
alr[nex]=false;
}
}
vis[x]=true;
len=Que[x].size();
for(int i=0; i<len; i++)
{
int nex=Que[x][i].nex;
int id=Que[x][i].id;
if(vis[nex]&&!ans[id])ans[id]=find(nex);
}
pre[x]=find(fa);
}
void init(int n)
{
for(int i=1; i<=n; i++)
pre[i]=i;
}
int main()
{
int n,q,cont=1;
char fa[50],son[50],name1[50],name2[50];
scanf("%d",&n);
init(n);
cont=1;
for(int i=0; i<n; i++)
{
scanf("%s%s",fa,son);
int idfa=mp[fa],idson=mp[son];
if(!idfa)
{
memcpy(re[cont],fa,sizeof(re[cont]));
idfa=mp[fa]=cont++;
}
if(!idson)
{
memcpy(re[cont],son,sizeof(re[cont]));
idson=mp[son]=cont++;
}
G[idfa].push_back(idson);
}
scanf("%d",&q);
for(int i=1; i<=q; i++)
{
scanf("%s%s",name1,name2);
int id1=mp[name1],id2=mp[name2];
t.id=i;
t.nex=id2;
Que[id1].push_back(t);
t.nex=id1;
Que[id2].push_back(t);
}
for(int i=1; i<cont; i++)
if(!vis[find(i)])
{
alr[find(i)]=true;
dfs(find(i),find(i));
}
for(int i=1; i<=q; i++)
printf("%s\n",re[ans[i]]);
}
LCT:
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define fa(x) tree[x].pre
#define grafa(x) tree[tree[x].pre].pre
struct bian
{
int nex,nex_node;
bian(int x=0,int y=0):
nex(x),nex_node(y) {}
} edge[1000005];
int head[500005],edge_num=0;
void add_edge(int now,int nex)
{
edge[edge_num]=bian(nex,head[now]);
head[now]=edge_num++;
}
int path_pre[500005];
void dfs(int x,int fa)
{
path_pre[x]=fa;
for(int i=head[x]; ~i; i=edge[i].nex_node)
{
int nex=edge[i].nex;
if(nex==fa)continue;
dfs(nex,x);
}
}
struct node
{
int pre,lson,rson;
int val,siz;
node(int pre=-1,int lson=-1,int rson=-1,
int val=0,int siz=0):
pre(pre),lson(lson),rson(rson),
val(val),siz(siz) {}
} tree[500005];
int root=-1;
void pushup(int x)
{
tree[x].siz=1;
if(~ls(x))
tree[x].siz+=tree[ls(x)].siz;
if(~rs(x))
tree[x].siz+=tree[rs(x)].siz;
}
void zig(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
ls(y)=rs(x);
if(~ls(y))fa(ls(y))=y;
rs(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void zag(int x)
{
int y=fa(x);
if(~fa(y))
if(ls(fa(y))==y)
ls(fa(y))=x;
else rs(fa(y))=x;
fa(x)=fa(y),fa(y)=x;
rs(y)=ls(x);
if(~rs(y))fa(rs(y))=y;
ls(x)=y;
if(fa(x)==-1)root=x;
pushup(y),pushup(x);
}
void splay(int x,int wz=-1)
{
while(x!=wz && fa(x)!=wz)
if(grafa(x)==wz)
if(ls(fa(x))==x)zig(x);
else zag(x);
else if(ls(fa(x))==x && ls(grafa(x))==fa(x))
zig(fa(x)),zig(x);
else if(rs(fa(x))==x && rs(grafa(x))==fa(x))
zag(fa(x)),zag(x);
else if(ls(fa(x))==x && rs(grafa(x))==fa(x))
zig(x),zag(x);
else if(rs(fa(x))==x && ls(grafa(x))==fa(x))
zag(x),zig(x);
}
int aux_root(int x)
{
while(~ls(x))x=ls(x);
return x;
}
int access(int x)
{
int deper=-1;
while(~x)
{
splay(x);
fa(rs(x))=-1;
rs(x)=deper;
pushup(x);
if(~deper)fa(deper)=x;
deper=x;
x=path_pre[aux_root(x)];
}
return deper;
}
int lca(int x,int y)
{
access(x);
return access(y);
}
void show(int n)
{
for(int i=1;i<=n;i++)
printf("%d: ls:%d rs:%d fa:%d\n",i,ls(i),rs(i),fa(i));
}
int main()
{
memset(head,-1,sizeof(head));
int n,q,root;
scanf("%d%d%d",&n,&q,&root);
for(int i=1; i<n; i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
dfs(root,-1);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
