欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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都讲数论了我还在更原来的博客。

慢工细活

努力嘻嘻

相关标签: ST表 LCA