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