社区讨论

为什么这样不行呢?求大佬解答

P3379【模板】最近公共祖先(LCA)参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@m237ffqu
此快照首次捕获于
2024/10/10 19:17
去年
此快照最后确认于
2025/11/04 17:30
4 个月前
查看原帖
我在写倍增的时候发现的问题
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,s,jump[N][21],head[N],tot,deep[N],bb;
struct node{
	int to,nxt;
}tu[2*N];
void add(int x,int y){
	tu[++tot].to=y;
	tu[tot].nxt=head[x];
	head[x]=tot;
}
void dfs(int x){
	for(int i=head[x];i;i=tu[i].nxt){
		int v=tu[i].to;
		if(v==jump[x][0]) continue;
		jump[v][0]=x;
		deep[v]=deep[x]+1;
		dfs(v);
	}
}
void init(){
	for(int i=1;(1<<i)<=n;i++){
		for(int j=1;j<=n;j++){
			jump[j][i]=jump[jump[j][i-1]][i-1];
		}
		bb=i;
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	int  kl=bb;
	while(deep[x]>deep[y]){
		if(jump[x][kl]==0||deep[jump[x][kl]]<deep[y]){
			kl--;
			continue;
		}
		x=jump[x][kl];
		kl--;
	}
	if(x==y) return x;
	kl=bb;
	while(kl){
		if(jump[x][kl]==jump[y][kl]){
			kl--;
			continue;
		}
		x=jump[x][kl],y=jump[y][kl];
		kl--;
	}
	return jump[x][0];
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	deep[s]=1;
	dfs(s);
	init();
	//cout<<"wuwu";
	while(m--){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
} 
这样只能过样例,把第43行改成
CPP
while(jump[x][0]!=jump[y][0])
就能过了,但是理论上来说他们跳到2^1后停止不应该也行吗

回复

6 条回复,欢迎继续交流。

正在加载回复...