[传智杯 #4 决赛] [yLOI2021] 生活在树上(hard version)

题目背景

**本题是 P8200 的较难版本,两道题目的解法略有不同。本题和 P8200 在题意上的区别在于本题给定树上的点权,而不是边权。** 小智生活在「传智国」,这是一个有 $n$ 个城市的国家,各个城市由 $n-1$ 条道路相连。 每个城市都有一个财富指数 $w_i$ ,我们定义,小智从城市 $a$ 走到城市 $b$ 的代价是 $\mathrm{dis}_{a, b} = \bigoplus \limits_{u \in \mathrm{path}\left(a, b\right)} w_u$,其中 $\bigoplus$ 表示**按位异或**(如果你不知道什么是**按位异或**,请参见题目下方的提示/说明),$\mathrm{path}\left(a,b\right)$ 表示 $a$ 到 $b$ 的简单路径上的点集(包括 $a$ 和 $b$)。也即 $\mathrm{dis}_{a, b}$ 表示将 $a$ 与 $b$ 的简单路径上所有点写作 $u_1, u_2, u_3, \dots$ 后,求 $w_{u_1} \bigoplus w_{u_2}\bigoplus w_{u_3} \dots$ 的结果。 有一天,小智获得了去参加传智杯的机会,他在前往比赛地的路上想到了一个问题,但他好像不会做,于是他把这个题告诉了你。聪明的同学,你可以帮帮他吗?

题目描述

小智说:「由于我们的国家只有 $n$ 个城市和 $n-1$ 条道路,那么我们的国家就相当于是一棵树。我在想,在我们的国家中,是否存在城市满足『到城市 $a$ 的代价和到城市 $b$ 的代价的异或等于 $k$』。好难哦,我想不出来,你能帮帮我吗?」 也就是说,给定城市 $a, b$ 和整数 $k$,请你计算是否存在城市 $t$ 满足 $\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} = k$。

输入输出格式

输入格式


第一行有两个整数 $n$,$m$,表示国家的城市数和询问的个数。 第二行有 $n$ 个整数 $w_i$,表示 $i$ 号城市的财富指数。 接下来 $n-1$ 行,每行有两个整数 $x, y$,表示城市 $x$ 与城市 $y$ 有一条边相连。 接下来 $m$ 行,每行有三个整数 $a, b, k$,表示小智从城市 $a$ 走到城市 $b$,$k$ 的含义与题目描述一致。

输出格式


输出共 $m$ 行。 对于第 $i$ 个询问,如果存在至少一个城市 $t$ 满足要求,则输出 `Yes`。 如果不存在任何一个城市满足条件,则输出 `No`。 输出字符串大小写不敏感,例如,`Yes`、`yES`、`YES`、`yes` 等都算作 `Yes`。

输入输出样例

输入样例 #1

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

输出样例 #1

nO
No
YeS

输入样例 #2

5 10
93 97 100 93 93
2 1
3 2
4 3
5 1
5 2 93
4 1 93
3 2 100
3 2 100
2 3 9999998
1 2 93
2 3 97
1 2 93
2 3 97
4 3 93

输出样例 #2

no
nO
yEs
yEs
No
yEs
yeS
YES
yES
yes

说明

### 相关概念解释 「树」:树是一个有 $n$ 个结点和 $n-1$ 条边的无向简单连通图。 「按位异或」:按位异或是一个二元运算,步骤是将两个数的二进制位按位比较,相同为 $0$,不同为 $1$ 。例如:$3 \bigoplus 5 = (011)_2 \bigoplus (101)_2 = (110)_2 = 6$。 ### 样例 1 解释 下图为传智国的地图。 $\forall t \in \{1, 2, 3, 4, 5\}$,都不可能有 $\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} = 4$,$\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 12$,于是输出 `No`; 而取 $t=4$,有 $\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 10$,于是输出 `Yes`。 ![](https://cdn.luogu.com.cn/upload/image_hosting/d3phj9di.png) ### 数据规模与约定 对于所有测试点,保证 $1 < n \leq 5 \times 10^5$,$1 \leq m \leq 5 \times 10^5$,$0 \leq w_i \leq 1\times 10^7$。 对于每次询问,保证 $1 \leq a,b \leq n$ 且 $a \neq b$,$0 \leq k \leq 1\times 10^7$。 ### 提示 - 请注意常数因子对程序效率造成的影响。 - 对于两个 $x, y \leq 10^7$,$x \bigoplus y$ 可能大于 $10^7$,请特别注意这一点。