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.
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 )
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.