Your Loss
Contest: Codeforces Round 956 (Div. 2) and ByteRace 2024
Difficulty rating: 3000
Tags: bitmasks, brute force, dp, trees

You are given a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$, along with an array of size $$$n$$$. The value of $$$i$$$-th node is $$$a_{i}$$$. There are $$$q$$$ queries. In each query, you are given 2 nodes numbered as $$$x$$$ and $$$y$$$.

Consider the path from the node numbered as $$$x$$$ to the node numbered as $$$y$$$. Let the path be represented by $$$x = p_0, p_1, p_2, \ldots, p_r = y$$$, where $$$p_i$$$ are the intermediate nodes. Compute the sum of $$$a_{p_i}\oplus i$$$ for each $$$i$$$ such that $$$0 \le i \le r$$$ where $$$\oplus$$$ is the XOR operator.

More formally, compute $$$$$$\sum_{i =0}^{r} a_{p_i}\oplus i$$$$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Each test case contains several sets of input data.

The first line of each set of input data contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of nodes.

The next $$$n-1$$$ lines of each set of input data contain $$$2$$$ integers, $$$u$$$ and $$$v$$$ representing an edge between the node numbered $$$u$$$ and the node numbered $$$v$$$. It is guaranteed that $$$u \ne v$$$ and that the edges form a tree.

The next line of each set of input data contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$) — values of the nodes.

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

The next $$$q$$$ lines describe the queries. The $$$i$$$-th query contains $$$2$$$ integers $$$x$$$ and $$$y$$$ ($$$1 \le x,y \le n$$$) denoting the starting and the ending node of the path.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$ and sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each query, output a single number — the sum from the problem statement.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
1
4
1 2
2 3
3 4
2 3 6 5
3
1 4
3 4
1 1

Example output:
14
10
2

Editorial:
We'll solve for each bit separately. Observe that the number of nodes contributing to the sum for a fixed bit $$$j$$$ is the sum of the bit xor'ed with an alternating pattern of $$$2^j$$$ continuous bits over the path, i.e., say for $$$j=2$$$, the bits are xor'ed with $$$0000111100001\ldots$$$. For the rest of the editorial, we will use the word "bit pattern" to refer to this binary string.
Let's root the tree arbitrarily and define $$$dp[u][j]$$$ as the number of nodes that contribute $$$2^j$$$ to the sum required in the query on the path from the node $$$u$$$ to the root. Notice that for $$$dp[u][j]$$$ the pattern $$$000\ldots0111\ldots1$$$ transitions from $$$0$$$ to $$$1$$$ at the $$$2^j$$$th ancestor of $$$u$$$. Hence, you can compute $$$dp[u][j]$$$ just by knowing the value of the $$$dp$$$ at the $$$2^j$$$th ancestor and its depth, and the sum of set bits on the remaining path. You can precompute all the power of two ancestors by binary jumping and calculate sums using root-to-node prefix sums.
Now, you need to keep track of a few variables to answer queries. Let there be a query from the node $$$u$$$ to the node $$$v$$$. We define $$$lc$$$ as $$$lca(u,v)$$$.
For a fixed bit $$$j$$$, let there be nodes $$$ux[j],vx[j]$$$ such that the path from $$$ux[j]$$$ to $$$vx[j]$$$ is the largest subpath of the path from $$$u$$$ to $$$v$$$ with $$$lc$$$ lying on this path and all the bits from the pattern being the same over this path. Let's call it the central path.
One more position to keep track of is the node $$$vy[j]$$$ such that it is the lowest ancestor of $$$v$$$ where the length of the path from $$$u$$$ to $$$vy$$$ is a multiple of $$$2^j$$$ and $$$vy$$$ lies on the path from $$$u$$$ to $$$v$$$. It is possible that this node does not exist. Notice that the bit pattern for $$$dp[vy][j]$$$ upwards will coincide or will be the exact opposite of the bit pattern for the query up to the node $$$lc$$$.
With these values computed, we can split the query path into separate paths; the answer for each can be easily calculated using prefix sums and precomputed $$$dp$$$ values:
• The path from $$$u$$$ to $$$ux[j]$$$.
• The path from $$$ux[j]$$$ to $$$vx[j]$$$.
• The path from $$$vx[j]$$$ to $$$vy[j]$$$.
• The path from $$$vy[j]$$$ to $$$v$$$.
To compute these three positions quickly, we will again use binary jumping, precomputing these for all queries. To compute $$$vy[j]$$$, we notice that for $$$vy[0] = v$$$. Then, we make binary jumps whenever necessary. For $$$ux[j]$$$ and $$$vx[j]$$$, we can start iterating from a bit larger than n to the smallest, noting that if $$$2^j >= n$$$, the endpoints will be $$$ux[j]=u$$$ and $$$vx[j]=v$$$. We make binary jumps when necessary, $$$vy[j]$$$ is also required for the computation.
Another alternative to binary jumping is to maintain a list of ancestors of the current node while running dfs on the tree and calculate these positions directly during the dfs for each query.