LCA,全RE+样例没过,求大佬查错
查看原帖
LCA,全RE+样例没过,求大佬查错
181037
ysmlwudia楼主2021/2/27 15:13
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<string.h>
#include<queue>
#define ll long long
#define debug cout<<"How badly it works!"<<endl;
using namespace std;
const int N=100060;
const int logn=20;
int n,m,last[N],tot,f[N][logn+1],xr[N][logn+1],dep[N];

struct edge{
	int prev,to,v;
}e[N];
void add(int a,int b,int c){
	e[++tot]={last[a],b,c};
	last[a]=tot;
}
void dfs(int x,int d){
	dep[x]=d;
	for(int i=last[x];i;i=e[i].prev){
		int y=e[i].to;
		if(!dep[y]){
			f[y][0]=x;
			xr[y][0]=e[i].v;
			dfs(y,d+1);
		} 
	}
}
int lca(int x,int y){
	int ans=0;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=logn;i>=0;i--){
		if(dep[x]-(1<<i)>=dep[y])ans^=xr[x][i],x=f[x][i];//要先异或再跳,因为x会变化,下面同理 
	}
	if(x==y)return ans;
	for(int i=logn;i>=0;i--){
		if(f[x][i]!=f[y][i])ans=ans^xr[x][i]^xr[y][i],x=f[x][i],y=f[y][i];
	}
	return ans^xr[x][0]^xr[y][0];//x和y实际上并非最近公共祖先,还差一层,f[x][0]和f[y][0]是 
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	cin>>m;
	f[1][0]=1;
	//xr[1][0]=0;
	dfs(1,1);
	for(int j=1;j<=logn;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
			xr[i][j]=xr[i][j-1]^xr[xr[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		cout<<lca(u,v)<<endl;
	}
	return 0;
}

2021/2/27 15:13
加载中...