Let's say we have some numbers. In -th bit of the numbers, if 1 appears times, this bit will contribute to the sum of the numbers. That is to say, for each bit , 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 , we can easily count the number of 1’s in each bit of all the values of . 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 to its child . What do we need to do? The effect of vertex on the subtree of vertex needs to be wiped away. So, if the -th bit of is 1, the value of -th bit of all 's will be altered (1’s will be 0’s, 0’s will be 1’s), where is any vertex of subtree . On the contrary, the effect of vertex needs to be added to the whole tree except the subtree of vertex (because it has already its effect on its subtree). So, if the -th bit of is 1, the value of -th bit of all 's will be altered where is any vertex of the tree except the subtree of . To switch back the root to vertex , 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 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 of all s. Let, there are numbers and in bit of the numbers, there are 1’s. If this bit is altered, the number of 1 in this bit will be . We need to use this property. While running DFS, we also need to keep track of if any bit of all s of the subtree of a vertex 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: , where is the most significant bit of the maximum .
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.