13号点re求调
查看原帖
13号点re求调
1125784
shuidianfei楼主2024/9/18 16:47

出现异常错误的13号点 采用欧拉序+st表的方法

#include<bits/stdc++.h>
#define MAX 500010
using namespace std;
int n,m,root,bfss=0;
int bfsmap[MAX];//bfs to num
int nummap[MAX];//num to bfs
int first[MAX];//first bfs to start
int start[MAX<<1],tail=0;//ou la xu
int st[MAX<<1][21];//ST
vector<int>tree[MAX];
void bfs(int fa,int son){
	bfss++;
	bfsmap[bfss]=son;
	nummap[son]=bfss;
	start[++tail]=nummap[son];
	first[son]=tail;
	for(int i=0;i<tree[son].size();i++)
		if(tree[son][i]!=fa){
			bfs(son,tree[son][i]);
			start[++tail]=nummap[son];
		}
	return;
}
void stinit(){
	for(int i=1;i<=tail;i++)
		st[i][0]=start[i];
	for(int i=1;i<=(int)log2(tail);i++)
		for(int j=1;j-1+(1<<i)<=tail;j++)
			st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
	return;
}
int ask(int son1,int son2){
	int l=min(first[son1],first[son2]),r=max(first[son1],first[son2]),k=log2(r-l);
	return min(st[l][k],st[r-(1<<k)][k]);
}
int main(){
	cin>>n>>m>>root;
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	bfs(0,root);
	stinit();
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",bfsmap[ask(x,y)]);
	}
	return 0;
}
2024/9/18 16:47
加载中...