新bug!!!!!!
  • 板块灌水区
  • 楼主shenlijia
  • 当前回复12
  • 已保存回复12
  • 发布时间2024/4/20 15:59
  • 上次更新2024/4/20 18:09:09
查看原帖
新bug!!!!!!
936841
shenlijia楼主2024/4/20 15:59
#include <bits/stdc++.h>
using namespace std;
int n,m,s,x,y,idx=1,head[500010],dpt[500010],fa[500010][19];
struct node{
	int to,next;
}edges[500010*2];
void add(int x,int y){
	edges[idx].to=y;
	edges[idx].next=head[x];
	head[x]=idx++;
} 
int dfs(int s,int f){
	for(int i=head[s];i;i=edges[i].next){
		int t=edges[i].to;
		if(t==f)continue;
		dpt[t]=dpt[s]+1;
		fa[t][0]=s;
		for(int i=1;i<=log2(dpt[t]);i++){
			fa[t][i]=fa[fa[t][i-1]][i-1];
		}
		dfs(t,s);
	}
}
int find(int x,int y){
	if(dpt[x]<dpt[y])swap(x,y);
	while(dpt[x]>dpt[y]){
		int p=log2(dpt[x]-dpt[y]);
		x=fa[x][p];
	}
	if(x==y)return x;
	for(int i=log2(dpt[x]);i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
	cin >> n >> m >> s;
	for(int i=0;i<n-1;i++){
		cin >> x >> y;
		add(x,y);
		add(y,x);
	}
	dpt[s]=0;fa[s][0]=-1;
	dfs(s,-1);
	while(m--){
		cin >> x >> y;
		cout << find(x,y) << endl;
	}
	return 0;
}

就是说P3379这道题(最近公共祖先)过不了,原因竟是dfs是int类型,求大神解释一下为什么
2024/4/20 15:59
加载中...