 # Count simple paths with XOR x

Can anyone please help me with this problem - Given a tree with N nodes count the number of simple paths between any nodes having bitwise xor of nodes in the simple path is x.
Each node has value associated with it.

N <=100000
val of each node <= 15
x <= 15

First for each node in the tree calculate the no. of time y appears in the subtree of that node , where y is xor of all node lying in the path from the root to that node , it could be done in O(N*15) .
Now the answer for root node = no of node in its subtree having x .
For non-root nodes z
Answer will be the no. Of nodes having x^y[parent[z]] in the subtree of node z + the no. Of nodes having x^value[z] in the answer calculated for the parent of z - the the no. of nodes having value x^value[z]^y[parent[z]] in the node z’s subtree.
( Not sure about the exact formula but the problem could be solved in this way )

2 Likes

Thank You.

What does y[parent[z]] denote here?

y is the xor till parent of z. He has just denoted that way don’t treat it as any indexing.

1 Like