A16289 | Trees and XOR Queries Again

You are given a tree consisting of $n$ vertices. There is an integer written on each vertex; the $i$ -th vertex has integer $a_i$ written on it.

You have to process $q$ queries. The $i$ -th query consists of three integers $x_i$ , $y_i$ and $k_i$ . For this query, you have to answer if it is possible to choose a set of vertices $v_1, v_2, \dots, v_m$ (possibly empty) such that:

- every vertex $v_j$ is on the simple path between $x_i$ and $y_i$ (endpoints can be used as well);
- $a_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i$ , where $\oplus$ denotes the bitwise XOR operator.

The first line contains one integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 2^{20} - 1$ ).

Then $n-1$ lines follow. Each of them contains two integers $u$ and $v$ ( $1 \le u, v \le n$ ; $u \ne v$ ) denoting an edge of the tree.

The next line contains one integer $q$ ( $1 \le q \le 2 \cdot 10^5$ ) — the number of queries.

Then $q$ lines follow. The $i$ -th of them contains three integers $x_i$ , $y_i$ and $k_i$ ( $1 \le x_i, y_i \le n$ ; $0 \le k_i \le 2^{20} - 1$ ).

For each query, print YES if it is possible to form a set of vertices meeting the constraints. Otherwise, print NO.

You can print each letter in any case.