Trees and XOR Queries Again
Contest: Educational Codeforces Round 159 (Rated for Div. 2)
Difficulty rating: 2400
Tags: data structures, dfs and similar, divide and conquer, graphs, implementation, math, trees

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.

Input format:
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$$$).

Output format:
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.

Constraints:
Time limit: 6.5 s
Memory limit: 512.0 MB

Example input:
4
0 1 2 10
2 1
3 2
4 2
8
3 3 0
3 4 1
3 4 7
1 3 1
1 3 2
1 3 10
1 4 10
1 4 11

Example output:
YES
YES
NO
YES
YES
NO
YES
YES

Editorial:
This problem requires working with XOR bases, so let's have a primer on them.
Suppose you want to solve the following problem: given a set of integers $$$x_1, x_2, \dots, x_k$$$ and another integer $$$y$$$, check whether it is possible to choose several (maybe zero) integers from the set such that their XOR is $$$y$$$. It can be solved with Gauss elimination method for systems of linear equations, but there are easier and faster methods, and we will describe one of them.
For the given set of integers, let's build an XOR base. An XOR base of a set of integers $$$X = \{x_1, x_2, \dots, x_k\}$$$ is another set of integers $$$A = \{a_1, a_2, \dots, a_m\}$$$ such that:
• every integer that can be expressed as the XOR of some integers from the set $$$X$$$ can also be expressed as the XOR of some integers from $$$A$$$, and vice versa;
• every integer in $$$A$$$ is non-redundant (i. e. if you remove any integer from $$$A$$$, the first property is no longer met).
For example, one of the XOR bases for $$$X = \{1, 2, 3\}$$$ is $$$A = \{1, 3\}$$$. $$$A = \{1, 2\}$$$ is also an XOR base of $$$X$$$, but $$$A = \{1, 2, 3\}$$$ is not since, for example, $$$2$$$ can be deleted.
Note that an XOR base is not necessarily a subset of the original set. For example, for $$$X = \{1, 2\}$$$, $$$A = \{1, 3\}$$$ is a valid XOR base.
Due to the laws of linear algebra, an XOR base of size $$$m$$$ supports $$$2^m$$$ integers (i. e. $$$2^m$$$ integers can be expressed using XOR of some numbers from the base). This means that since in our problem the integers are limited to $$$20$$$ bits, the maximum size of an XOR base we need is $$$20$$$.
Now let's talk about how we build, store and maintain the XOR base. We will use an array of $$$20$$$ integers, initially filled with zeroes (an array of all zeroes represents an empty XOR base). Let's call this array $$$b$$$. If some integer $$$b_i$$$ in this array is non-zero, it has to meet the following constraints:
• the $$$i$$$-th bit is set to $$$1$$$ in $$$b_i$$$;
• the $$$i$$$-th bit is set to $$$0$$$ in every integer $$$b_j$$$ such that $$$j < i$$$.
This is kinda similar to how the Gauss elimination method transforms a matrix representing the system of linear equations: it leaves only one row with non-zero value in the first column and puts it as the first row, then in the next non-zero column it leaves only one row with non-zero value (except for maybe the first row) and puts it as the second row, and so on.
Okay, we need to process two types of queries for XOR bases:
• add an integer and change the XOR base accordingly if needed;
• check that some integer is supported (i. e. can be represented) by the XOR base.
For both of those queries, we will use a special reduction process. In the model solution, it is the function reduce(b,x) that takes an array $$$b$$$ representing the XOR base and an integer $$$x$$$, and tries to eliminate bits set to $$$1$$$ from $$$x$$$. In this reduction process, we iterate on bits from $$$19$$$ (or the highest bit the number can have set to $$$1$$$) to $$$0$$$, and every time the bit $$$i$$$ we're considering is set to $$$1$$$, we try to make it $$$0$$$ by XORing $$$x$$$ with $$$b_i$$$. It can be easily seen that due to the properties of XOR base, XORing with $$$b_i$$$ is the only way to do it: if we XOR with any other number $$$b_j$$$ such that $$$j < i$$$, it won't affect the $$$i$$$-th bit; and if we XOR it with $$$b_j$$$ such that $$$j > i$$$, it sets the $$$j$$$-th bit to $$$1$$$ (and we have already ensured that it should be $$$0$$$).
If reduce(b,x) transforms $$$x$$$ to $$$0$$$, then $$$x$$$ is supported by the XOR base, otherwise it is not. And if we want to try adding $$$x$$$ to the base, we can simply reduce $$$x$$$, find the highest non-zero bit in the resulting integer $$$x'$$$, (let it be $$$i$$$), and assign $$$b_i$$$ to $$$x'$$$ (it is guaranteed that $$$b_i$$$ was zero, since otherwise we would have eliminated the $$$i$$$-th bit).
So, that's how we can work with XOR bases and process every query to them in $$$O(B)$$$, where $$$B$$$ is the number of bits in each integer.
Now let's go back to the original problem. Basically, for every query, we have to build a XOR base on some path in the tree. We can root the tree and then use LCA to split this path into two vertical paths, get XOR bases from those two paths, and merge them in $$$O(B^2)$$$. But how do we get an XOR base on a vertical path in something like $$$O(B^2)$$$?
To do this, for each vertex $$$v$$$, let's consider the following process. We go from $$$v$$$ to the root, maintain the XOR base of the integers we met, and every time we add something to the XOR base, we mark the current vertex as "interesting" for $$$v$$$. Our goal is to build a list of "interesting" vertices for $$$v$$$ in order from $$$v$$$ to the root. Since the size of each XOR base is up to $$$20$$$, the size of each such list is also up to $$$20$$$, so we can get the XOR base for a vertical path by simply iterating on that interesting list for the lower endpoint of the path.
Okay, the last part of the problem we have to solve is how to build these lists for all vertices in reasonable time. The key insight here is that if $$$p$$$ is the parent of $$$v$$$, then the list for $$$v$$$ will be very similar to the list for $$$p$$$:
• if $$$v$$$ is not supported by the XOR base of the list for $$$p$$$, then the list for $$$v$$$ is simply the list for $$$p$$$, with the vertex $$$v$$$ added;
• otherwise, $$$v$$$ eliminates one of the vertices from the list for $$$p$$$. We can find which one by building the XOR base for $$$v$$$ and the list of $$$p$$$; we need to add $$$a_v$$$ first, and then the values from all vertices in the list of $$$p$$$ in order "from bottom to top", and when an interesting vertex for $$$p$$$ adds nothing to the XOR base, it means that it is exactly the vertex we need to eliminate.
Combining all of these, we can get a solution that works in $$$O(nB^2)$$$ for preprocessing and in $$$O(B^2 + \log n)$$$ to answer each query.