自动搬运

查看原文

来自洛谷，原作者为

	MeowScore 灌水Q群：782534512（欢迎来玩）

搬运于2025-08-24 22:36:52，当前版本为作者最后更新于2022-03-12 21:38:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传送门 qwq

这是一道黄题，显然出题人想让我们用很简单的办法秒掉这道题，所以我使用树剖套线段树。

考虑异或的性质，如果一条边的权值被异或两遍，就相当于没异或。

再来看这道题。对于一次询问 $(x,y,k)$，我们任取一个点 $t$，如果 $t$ 不在 $x$ 到 $y$ 的链上，设沿着 $t$ 向上或向下走，首次到达 $x$ 到 $y$ 的链上时处于点 $p$，则：

$$dis_{x,t}\oplus dis_{y,t}=dis_{x,p}\oplus dis_{y,p}\oplus dis_{t,p}\oplus dis_{t,p}=dis_{x,y} $$

如果 $t$ 在 $x$ 到 $y$ 的链上，显然：

$$dis_{x,t}\oplus dis_{y,t}=dis_{x,y}$$

发现柿子是一样的。

于是发现对于这个查询，我们只要判断 $x$ 到 $y$ 这条链上的异或和是否等于 $k$ 就好了。树剖套线段树，线段树维护区间异或和即可。

代码：

#include<bits/stdc++.h>
using namespace std;
unsigned long long read(){
	unsigned long long ss=0,ww=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			ww=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ss=ss*10+ch-'0';
		ch=getchar();
	}
	return ss*ww;
}
int readi(){
	int ss=0,ww=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			ww=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ss=ss*10+ch-'0';
		ch=getchar();
	}
	return ss*ww;
}
int n,m;
const int N=500010;
int head[N],nex[N*2],to[N*2],cnt;
unsigned long long e[N*2];
void add(int x,int y,unsigned long long z){
	cnt++;
	nex[cnt]=head[x];
	to[cnt]=y;
	e[cnt]=z;
	head[x]=cnt;
}
unsigned long long a[N],t[N];
unsigned long long st[N*4];
int sz[N],son[N],tp[N],fa[N],dfn[N],dep[N],tot;
void dfs1(int x,int f){
	fa[x]=f;
	dep[x]=dep[fa[x]]+1;
	sz[x]=1;
	int maxn=-1;
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==f)
			continue;
		t[y]=e[i];
		dfs1(y,x);
		sz[x]+=sz[y];
		if(sz[y]>maxn){
			maxn=sz[y];
			son[x]=y;
		}
	}
}
void dfs2(int x,int top){
	tp[x]=top;
	tot++;
	dfn[x]=tot;
	a[tot]=t[x];
	if(son[x])
		dfs2(son[x],top);
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==fa[x]||y==son[x])
			continue;
		dfs2(y,y);
	}
}
unsigned long long res;
void build(int root,int l,int r){
	if(l==r){
		st[root]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	st[root]=st[root*2]^st[root*2+1];
}
void ask(int root,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		res=(res^st[root]);
		return;
	}
	int mid=(l+r)/2;
	if(mid>=x)
		ask(root*2,l,mid,x,y);
	if(mid+1<=y)
		ask(root*2+1,mid+1,r,x,y);
}
int main(){
	n=readi();
	m=readi();
	for(int i=1;i<n;i++){
		int x,y;
		unsigned long long z;
		x=readi();
		y=readi();
		z=read();
		add(x,y,z);
		add(y,x,z);
	}
	dfs1(1,1);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int x,y;
		unsigned long long k;
		x=readi();
		y=readi();
		k=read();
		res=0;
		while(tp[x]!=tp[y]){
			if(dep[tp[x]]<dep[tp[y]])
				swap(x,y);
			ask(1,1,n,dfn[tp[x]],dfn[x]);
			x=fa[tp[x]];
		}
		if(x!=y){
			if(dep[x]>dep[y])
				swap(x,y);
			ask(1,1,n,dfn[x]+1,dfn[y]);
		}
		if(res==k)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}