2543. 简单的树论问题
1000ms
512MB
简单
题目描述
给定一棵 $n$ 个结点的树，边有边权。
定义一条路径 $(u,v)$ 的权值 $w(u,v)$ 是 $u$ 到 $v$ 简单路径上所有边的按位异或和。
你要回答 $q$ 次询问，每次给出三个数 $x,y,z$，回答是否存在一个点 $s$，使得 $w(x,s)~\mathrm{xor}~w(y,s) = z$。这里 $\mathrm{xor}$ 表示按位异或运算。
输入格式
输入均为整数。
第一行：$n,q$。
第 $2$ 到第 $n$ 行：每行 $u,v,l$ 表示一条边连接 $u,v$，边权为 $w$。
接下来 $q$ 行：每行 $x,y,z$ 表示一次询问。
输出格式
对每组询问，如果存在 $s$，输出 `Yes`，否则输出 `No`。
每个输出占一行。
输出的大小写不敏感。如 `yES` 也算作 `Yes`。
样例 1
输入 (Input)
输出 (Output)
对于所有测试点，保证 $1 < n \leq 5 \times 10^5$，$1 \leq q \leq 5 \times 10^5$，$0 \leq l < 2^{64}$。
对于每次询问，保证 $1 \leq x, y \leq n$ 且 $a \neq b$，$0 \leq z < 2^{64}$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功