样例莫名不过求调
查看原帖
样例莫名不过求调
835809
T_TLucas_Yin楼主2024/4/27 19:01
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,l,r;
int ver[200005],ne[200005],head[200005],w[200005],tot;
void add(int x,int y,int z){
	ver[++tot]=y,ne[tot]=head[x],w[tot]=z,head[x]=tot;
}
int d[200005],fat[200005],son[200005],siz[200005],a[200005];
void dfs1(int x,int fa,int k){
	d[x]=k,fat[x]=fa,son[x]=-1,siz[x]=1;
	for(int i=head[x];~i;i=ne[i]){
		if(ver[i]==fa) continue;
		a[ver[i]]=w[i];
		dfs1(ver[i],x,k+1);
		siz[x]+=siz[ver[i]];
		if(son[x]==-1||siz[ver[i]]>siz[son[x]]) son[x]=ver[i];
	}
}
int df[200005],b[200005],top[200005],dfn;
void dfs2(int x,int fa,int k){
	df[x]=++dfn,b[dfn]=a[x],top[x]=k;
	if(!son[x]) return;
	dfs2(son[x],x,k);
	for(int i=head[x];~i;i=ne[i]){
		if(ver[i]==son[x]||ver[i]==fa) continue;
		dfs2(ver[i],x,ver[i]);
	}
}
int f[500005];
void build(int root,int l,int r){
	if(l==r){ f[root]=b[l];return; }
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	f[root]=f[root<<1]^f[root<<1|1];
}
int Find(int root,int l,int r,int fl,int fr){
	if(fl<=l&&r<=fr) return f[root];
	int mid=(l+r)>>1,sum=0;
	if(fl<=mid) sum^=Find(root<<1,l,mid,fl,fr);
	if(fr>mid) sum^=Find(root<<1|1,mid+1,r,fl,fr);
	return sum;
}
int query(int x,int y){
	int sum=0;
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]]) swap(x,y);
		sum^=Find(1,1,n,df[top[x]],df[x]);
		x=fat[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	if(x!=y) sum^=Find(1,1,n,df[x]+1,df[y]);
	return sum;
}
int main(){
	scanf("%d",&n);
	memset(head,-1,sizeof(head));
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	scanf("%d",&m);
	dfs1(1,0,1);
	dfs2(1,0,1);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&l,&r);
		printf("%d\n",query(l,r));
	}
	return 0;
}
2024/4/27 19:01
加载中...