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.