XOR Tree

Let's say we have some numbers. In $b$-th bit of the numbers, if 1 appears $c$ times, this bit will contribute $(c\times2^b)$ to the sum of the numbers. That is to say, for each bit $b$, if we know how many times 1 appears in that bit, we can easily calculate the sum. This is one of the key observations to solve this problem.

From now on, we will call the special vertex the root of the tree. If the tree has a fixed root $u$, we can easily count the number of 1’s in each bit $b$ of all the values of $G(v)$. To count them when another vertex will be the root vertex, we can apply the re-rooting technique.

Let's say, we want to switch the root from vertex $u$ to its child $v$. What do we need to do? The effect of vertex $u$ on the subtree of vertex $v$ needs to be wiped away. So, if the $b$-th bit of $A_u$ is 1, the value of $b$-th bit of all $G(x)$'s will be altered (1’s will be 0’s, 0’s will be 1’s), where $x$ is any vertex of subtree $v$. On the contrary, the effect of vertex $v$ needs to be added to the whole tree except the subtree of vertex $v$ (because it has already its effect on its subtree). So, if the $b$-th bit of $A_v$ is 1, the value of $b$-th bit of all $G(x)$'s will be altered where $x$ is any vertex of the tree except the subtree of $v$. To switch back the root to vertex $u$, just doing these things again is enough due to XOR’s property (find out yourself).

In each time of re-rooting, altering the values of $G(x)$ will cause TLE. Actually, we don't need to do this. As we need to calculate the sum, we only need to count the number of 1’s in each bit $b$ of all $G(x)$s. Let, there are $m$ numbers and in bit $b$ of the numbers, there are $k$ 1’s. If this bit is altered, the number of 1 in this bit will be $(m-k)$. We need to use this property. While running DFS, we also need to keep track of if any bit $b$ of all $G(x)$s of the subtree of a vertex $v$ needs to be altered or not. By managing these, we can easily calculate the new count of 1’s while re-rooting. Re-rooting needs to be done while traversing the tree by DFS.

Complexity: $O((V+E)\times B)$, where $B$ is the most significant bit of the maximum $A_i$.

P.S: A segment tree (using discovery time in a DFS) with lazy can also be used to alter the bits and count the 1’s. But you may need to be careful about the total number of update and query operations as they may cause TLE.