BREAKING EDGES
Hello, can anyone please help me with this problem on HackerEarth.
I am not able to think of the logic…only able to solve it through the naive approach , but it would result in TLE.
It would be a great help if anyone could help.!
Thanks in advance!
Okay make few observations.
Let us root the tree. When you break an edge, the tree breaks into the subtree of that edge, and the rest of the tree.
Next observation. The “or” of both the trees should be equal. So that means the “or” of the full tree will also be equal to that. So we want the “or” of both the subtree and the rest of the tree to be equal to the “or” of the full tree.
So let us consider a subtree. We can count the number of nodes in it’s subtree that have the ith bit set in O(n). Let us say this bit appears x times in the tree. If x=0, then this bit doesn’t appear and is irrelevant. If it does, then the number of times it appears in the subtree, y, should satisfy 0<y<x.
This makes sure the bit appears in both the subtree and the rest of the tree. If this is true for all bits, that means this is one edge that can be broken.
thanks a lot !! 