题目链接

F1. 生活在树上（easy version）

题目背景

本题是 B 组的最后一题，是 F2 题的简单版本，两道题目的解法略有不同。本题和 F2 题在题意上的区别在于本题给定树上的边权，而不是点权。

小智生活在「传智国」，这是一个有 nnn 个城市的国家，各个城市由 n−1n-1n−1 条道路相连。

每个道路都有长度 wiw_iwi​ ，我们定义，小智从城市 aaa 走到城市 bbb 的代价是 disa,b=⨁e∈path(a,b)we\mathrm{dis}_{a, b} = \bigoplus \limits_{e \in \mathrm{path}\left(a, b\right)} w_edisa,b​=e∈path(a,b)⨁​we​，其中 ⨁\bigoplus⨁ 表示按位异或（如果你不知道什么是按位异或，请参见题目下方的提示/说明），path(a,b)\mathrm{path}\left(a,b\right)path(a,b) 表示 aaa 到 bbb 的简单路径上的边集。也即 disa,b\mathrm{dis}_{a, b}disa,b​ 表示将 aaa 与 bbb 的简单路径上所有边写作 e1,e2,e3,…e_1, e_2, e_3, \dotse1​,e2​,e3​,… 后，求 we1⨁we2⨁we3…w_{e_1} \bigoplus w_{e_2}\bigoplus w_{e_3} \dotswe1​​⨁we2​​⨁we3​​… 的结果。

有一天，小智获得了去参加传智杯的机会，他在前往比赛地的路上想到了一个问题，但他好像不会做，于是他把这个题告诉了你。聪明的同学，你可以帮帮他吗？

题目描述

小智说：「由于我们的国家只有 nnn 个城市和 n−1n-1n−1 条道路，那么我们的国家就相当于是一棵树。我在想，在我们的国家中，是否有城市满足『到城市 aaa 的代价和到城市 bbb 的代价的异或等于 kkk』。好难哦，我想不出来，你能帮帮我吗？」

形式化的，给定城市 a,ba, ba,b 和整数 kkk，请你计算有哪几个城市 ttt 满足 dist,a⨁dist,b=k\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} = kdist,a​⨁dist,b​=k。

输入格式

第一行有两个整数 nnn，mmm，表示国家的城市数和询问的个数。

接下来 n−1n-1n−1 行，每行有两个整数 x,y,lx, y, lx,y,l，表示城市 xxx 与城市 yyy 有一条长度为 lll 的边。

接下来 mmm 行，每行有三个整数 a,b,ka, b, ka,b,k，表示小智从城市 aaa 走到城市 bbb，kkk 的含义与题目描述一致。

输出格式

共 mmm 行，每行一个整数。

对于第 iii 个询问，如果存在至少一个城市 ttt 满足要求，则输出 Yes。

如果不存在任何一个城市满足条件，则输出 No。

输出字符串大小写不敏感，例如，Yes、yES、YES、yes 等都算作 Yes。

样例 #1

样例输入 #1

5 3
1 2 2
1 3 6 
2 4 8
2 5 1
1 2 4
2 3 12
1 4 10

样例输出 #1

nO
No
YeS

样例 #2

样例输入 #2

5 10
2 1 63
3 1 57
4 2 2
5 2 84
5 2 84
4 1 9977404983223574764
2 5 84
2 1 15996060349666123522
5 4 86
3 1 8428615422876116375
5 1 107
2 3 6
2 3 6
4 2 2

样例输出 #2

yeS
nO
YEs
No
YEs
nO
YEs
yeS
yeS
YEs

提示

相关概念解释

「树」：树是一个有 nnn 个结点和 n−1n-1n−1 条边的无向简单连通图。

「按位异或」：按位异或即 C++、python、java 语言中的 「^」 运算。它是一个二元运算，步骤是将两个数的二进制位按位比较，相同为 000，不同为 111。例如：3⨁5=(011)2⨁(101)2=(110)2=63 \bigoplus 5 = (011)_2 \bigoplus (101)_2 = (110)_2 = 63⨁5=(011)2​⨁(101)2​=(110)2​=6。请注意，这是一个按位运算，不是一个逻辑运算。

样例 1 解释

下图为传智国的地图。

∀t∈{1,2,3,4,5}\forall t \in \{1, 2, 3, 4, 5\}∀t∈{1,2,3,4,5}，都不可能有 dist,1⨁dist,2=4\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} = 4dist,1​⨁dist,2​=4，dist,2⨁dist,3=12\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 12dist,2​⨁dist,3​=12，于是输出 No；

而取 t=5t = 5t=5，有 dist,1⨁dist,4=10\mathrm{dis}_{t, 1} \bigoplus \mathrm{dis}_{t, 4} = 10dist,1​⨁dist,4​=10，于是输出 Yes。

数据规模与约定

对于所有测试点，保证 1

对于每次询问，保证 1≤a,b≤n1 \leq a,b \leq n1≤a,b≤n 且 a≠ba \neq ba​=b，0≤k<2640 \leq k < 2^{64}0≤k<264。
思路：
首先需要明确的是和异或的特点，两个相同的数异或的结果为0,任何数异或0之后的仍旧是它本身。所以这道题目，需要注意的就是树的存储方式。只要能选中任何一个点作为起点，计算完到其他n-1个点的异或的结果，就能知道是否满足给定的条件。
代码：

#include 
using namespace std;
const int maxn=5e5+11;
#define ll unsigned long long 
int n,m;
ll dis[maxn];
bool flag[maxn];
struct edge
{int to;ll v;
};
vector e[maxn];
void dfs(int x)
{for(int i=0;ill y=e[x][i].to,z=e[x][i].v;if(flag[y]) continue;dis[y]=dis[x]^z;flag[y]=1;dfs(y);}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;iint x,y;ll z;scanf("%d%d%llu",&x,&y,&z);e[x].push_back({y,z});e[y].push_back({x,z});}flag[1]=1;dfs(1);//for(int i=1;i<=n;i++) cout<<"i="<int a,b;ll k;scanf("%d%d%llu",&a,&b,&k);//cout<<"dis[a]^dis[b="<<(dis[a]^dis[b])<