T0. xor
We need to know that a^a==0.
So what does it mean?
It means we can use prefix sum to solve it!
For 2 prefix sum S_i and $Sj, if we can solveS{i-1} \operatorname{opt}^{-1} Sj, we can solve\sum{k=i}^j Ak, since(\sum{k=1}^j Ak ) \operatorname{opt}^{-1} (\sum{k=1}^{i-1} Ak) = \sum{k=1}^{i-1} (A_k \operatorname{opt}^{-1} Ak) \operatorname{opt} \sum{k=i}^j Ak = \sum{k=i}^j A_k$
However, how can we apply this method to the tree?
Notice that there is no cycles in the tree, so if we denote a node as the root, there is always only 1 possible path from the root to any other node.
So, if the edges has weight… we can consider it as a sequence!
Method :
- Compute the prefix sum of each node. Complexity : O(n)
- For every queries, directly solve their xor. Complexity : O(q)
Complexity : O(n+q)