You are given the following:
A tree T consisting of n nodes
An integer x
Each node has some value w[i] associated with it.
Task
Determine the number of simple paths in the tree, such that the bitwise xor of elements on the simple path is x.
Note: A simple path between node u and v is defined as a sequence of edges that connects node u and v and includes the occurrence of a node at most once.
Example
Assumptions
n = 3
w = [3,2,2]
edges = [(1,2), (1,3)]
x = 1
Approach
There exist two simple paths such that bitwise xor of elements on the path is x
Two paths are from node 1 to node 2, 3 ^ 2 = 1 and node 1 to node 3, 3 ^ 2 = 1, where ^ is Bitwise Xor operator.
Therefore, print 2.