CF1902F Trees and XOR Queries Again

给定一棵包含 $n$ 个顶点的树。每个顶点上写有一个整数，第 $i$ 个顶点上写有整数 $a_i$。 你需要处理 $q$ 个询问。第 $i$ 个询问包含三个整数 $x_i$、$y_i$ 和 $k_i$。对于每个询问，你需要回答是否存在一个顶点集合 $v_1, v_2, \dots, v_m$（可以为空），满足： - 每个顶点 $v_j$ 都在从 $x_i$ 到 $y_i$ 的简单路径上（可以包含端点）； - $a_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i$，其中 $\oplus$ 表示按位异或运算。

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2^{20} - 1$）。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示树上的一条边。 下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示询问的数量。 接下来 $q$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $k_i$（$1 \le x_i, y_i \le n$，$0 \le k_i \le 2^{20} - 1$）。

对于每个询问，如果存在满足条件的顶点集合，输出 YES，否则输出 NO。 你可以以任意大小写输出每个字母。

由 ChatGPT 4.1 翻译