简介
最近公共祖先 \(lca(a,b)\) 指的是a到根的路径和b到n的路径的深度最大的公共点.
定理. 以 \(r\) 为根的树上的路径 \((a,b) = (r,a) + (r,b) - 2 * (r,fa(lca))\). (树上差分)
求法
tarjan
离线算法, 总时间 \(O(n+q)\). (q表示询问次数)
//利用前向星存储询问
struct te{int t,pr,lca;}edge[1000050],qedge[1000050];
int head[500050],pe=1,qhead[500050],pq=1;
void adde(int f,int t){
edge[++pe].t=t;
edge[pe].pr=head[f];
head[f]=pe;
}
void addq(int f,int t){
qedge[++pq].t=t;
qedge[pq].pr=qhead[f];
qhead[f]=pq;
}
//并查集
int fa[500050];
int find(int p){return p==fa[p]?p:fa[p]=find(fa[p]);}
void merge(int l,int r){fa[r]=l;}//merge r to l
//tarjan
int vi[500050];
void tar(int p){
vi[p]=1;
for(int i=head[p];i;i=edge[i].pr){
if(vi[edge[i].t])continue;
tar(edge[i].t);
merge(p,edge[i].t);
}
for(int i=qhead[p];i;i=qedge[i].pr)
if(vi[qedge[i].t])
qedge[i].lca=qedge[i^1].lca=find(qedge[i].t);
}
倍增
\(O(n\log n)\)预处理, \(O(\log n)\) 查询, \(O(n\log n)\)空间. 由于利用结合律, 可以维护一些链上信息. 可以动态维护.
int fa[nsz][20],dep[nsz]{-1};
//动态维护
void addfa(int p,int f){
dep[p]=dep[f]+1;
fa[p][0]=f;
rep(i,1,18)fa[p][i]=fa[fa[p][i-1]][i-1];
}
//静态
void init(){
dfs(1,0); //get fa[i][0]
rep(i,1,18)rep(j,1,n)fa[j][i]=fa[fa[j][i-1]][i-1];
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
repdo(i,18,0)if(dep[fa[a][i]]>=dep[b])a=fa[a][i];
if(a==b)return a;
repdo(i,18,0)if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
欧拉序+rmq
\(O(n\log n)\)预处理, \(O(1)\) 查询, \(O(n\log n)\)空间.
int l2n[nsz*3+50];
int eul[nsz*3],cnt=0,vis[nsz],d[nsz];
int stt[nsz*3][21];
void dfs(int u,int fa){
eul[++cnt]=u;
if(vis[u]==0)vis[u]=cnt,d[u]=d[fa]+1;
for(int i=hd[u],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){
if(v==fa)continue;
dfs(v,u);
eul[++cnt]=u;
}
}
int dmin(int a,int b){return d[a]<=d[b]?a:b;}
void rmq(){
rep(i,1,cnt)stt[i][0]=eul[i];
rep(j,1,l2n[pe]){
rep(i,1,pe+1-(1<<j)){
stt[i][j]=dmin(stt[i][j-1],stt[i+(1<<(j-1))][j-1]);
}
}
}
int stqu(int a,int b){
int l=l2n[b-a+1];
return dmin(stt[a][l],stt[b-(1<<l)+1][l]);
}
void eulinit(){
int l=0;
rep(i,1,n*3){
if(i==(1<<(l+1)))++l;
l2n[i]=l;
}
dfs(s,0);
rmq();
}
int lca(int a,int b){
int x=vis[a],y=vis[b];
if(x>y)swap(x,y);
return stqu(x,y);
}
树链剖分
\(O(n)\)预处理, \(O(\log n)\) 查询, \(O(n)\)空间. 由于利用结合律, 可以维护一些链上信息.
int dep[nsz],sz[nsz],son[nsz],fa[nsz],top[nsz];
void dfs1(int p,int f){
sz[p]=1,dep[p]=dep[f]+1,fa[p]=f;
for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){
if(v==f)continue;
dfs1(v,p);
sz[p]+=sz[v];
if(son[p]==0||sz[son[p]]<sz[v])son[p]=v;
}
}
void dfs2(int p,int tv){
top[p]=tv;
if(son[p])dfs2(son[p],tv);
for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){
if(v==fa[p]||v==son[p])continue;
dfs2(v,v);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}