ST表求LCA
程序员文章站
2024-01-14 16:26:28
...
ST表求LCA
好多天前写的……
dfs一遍,得到特殊的长度为 2*n-1 dfs序,然后维护一个在dfs序上的区间深度最小值,而拥有这个最小深度值的节点就是我们要求的LCA。
简单易懂。
#include<bits/stdc++.h>
#define RG register
using namespace std;
const int N=500000+5,P=20;
int to[N<<1],head[N<<1],nxt[N<<1],cn;
int logbx[N<<1],stu[N<<1][P+5];
int seq[N<<1],dep[N<<1],pos[N<<1];
int n,m,root,x,y,idc;
void create(int u,int v){
cn++;
to[cn]=v;
nxt[cn]=head[u];
head[u]=cn;
}
void init(){
logbx[0]=-1;
for(RG int i=1;i<N;i++)
logbx[i]=logbx[i>>1]+1;
for(RG int p=0;p<=P;p++)
for(RG int i=1;i+(1<<p)-1<=idc;i++)//i+(1<<p)-1<=idc惨痛教训!
if(p==0)
stu[i][p]=seq[i];//stu[i][p]=seq[i]惨痛教训!
else{
int l=stu[i][p-1],r=stu[i+(1<<(p-1))][p-1];//位运算一定要打上括号!吃屎吧优先级!
stu[i][p]=dep[l]<dep[r]?l:r;
}
}
void dfs(int u,int f){
int v;
for(RG int i=head[u];i;i=nxt[i]){
v=to[i];
if(v==f) continue;
seq[++idc]=v;//!!
pos[v]=idc;//!!
dep[v]=dep[u]+1;
dfs(v,u);
seq[++idc]=u;
pos[u]=idc;
}
}
int LCA(int u,int v){
u=pos[u],v=pos[v];
if(u>v) u^=v^=u^=v;
int d=logbx[v-u+1];
int x=stu[u][d],y=stu[v-(1<<d)+1][d];
return dep[x]<dep[y]?x:y;
}
int main(){
scanf("%d%d%d",&n,&m,&root);
for(RG int i=1;i<=n-1;i++){
scanf("%d%d",&x,&y);
create(x,y);
create(y,x);
}
seq[++idc]=root;
dep[root]=1;
dfs(root,root);
init();
for(RG int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
printf("%d\n",LCA(x,y));
}
return 0;
}
ok,我还要更好多csdn啊。idy002都讲数论了我还在更原来的博客。
慢工细活
努力嘻嘻
上一篇: LCA RMQ ST表优化 模板
下一篇: 利用RMQ -ST求 LCA