This question appeared in icpc regionals dhaka 2017. Click here for the question.
My approach to solve the problem is to traverse the tree once using DFS considering any node as the root and maintaining the xor distance along a path from the root. Since the edge weights cant exceed 2^16-1, every xor distance can be hashed in an array storing its frequency as the value.
Now the problem reduces to finding pairs of numbers whose xor is equal to x, for all 0<=x<=2^16-1. Let say the pair of numbers are a and b. Then if a ⊕ b= x, then x ⊕ a = b. Hence for every a present in the hashmap frequency of b can be found and finding the count of pairs accordingly. Do this for all 0<= x <=2^16-1.
this turns out to be O(2^32),which is not feasible. Please suggest some alternate approach for finding count of such pairs or a different solution altogether for this problem.
You just need to do a xor convolution on the array you found :)
Hmm, I dont know what xor convolution is. But thanks for the hint, I'll read about it. :)
I guess he means folding with XOR. Like an array sum, but with
^instead of+. Folding could be defined for any binary operation. For example,min_elementandmax_elementfrom<algorithm>are also folds, their binary operators areminandmaxrespectively.Suppose you have two arrays a, b. Then their XOR convolution is -
The sum is taken over all valid i and j.
If it was + operator then you could calculate this convolution with FFT. But here you can use Fast Walsh Hadamart Transform, you can learn about that here — Fast Fourier Transform and Variations of it
However, And-convolution, Or-convolution is also possible by the way.