At first, let’s take any arbitrary node as the root of the tree.
Let, where is any node of the tree. We can observe that the where and are two different nodes of the tree. This works because we can write where is the LCA (Lowest Common Ancestor) of node and node . So, .
It means for each query, if we can calculate for all possible such that both and lie on the simple path between node and node , we can get our desired answer. But how can we do this? Let’s say we store the values of for all possible in an array . Now if we calculate for all possible , we get the all possible costs. In this approach will also be calculated and will be calculated twice. So, we need to eliminate them later.
But this approach obviously won’t fit within the time limit. Now, what can we do? We can notice that the maximum value of any weight is only . We can use this. As which is calculated using xor operation and the maximum weight is , the value of any will also be . Let’s say the array stores the frequency of each element of the array . We can apply xor convolution on the array with itself using FWHT (Fast Walsh–Hadamard Transform). Then we will get the frequency array of all possible . We need to eliminate the count of and double count of after that. Now if we have this final frequency, we can easily calculate our final answer from that.
For generating the array , we can maintain a 2D array where stores the frequency of the value in where is any node lies on the path between node and the root. Then for any node and , if we know the we can easily generate the array using the array. This is left for the contestants.
Complexity: in each query, where taking is enough.