The problem goes like this. Given a tree rooted at node 1, N nodes with each node having a value Ai associated with it. Tell the number of edges in the tree which , when cut, will give 2 smaller trees whose bitwise OR of values of nodes are equal. Problem link
and the question is…? Have you tried something? Where exactly are you stuck? I can see you are thinking about dfs and that sounds as a good starting point. Have you been thinking about XOR properties?
[EDIT] sorry, I read XOR, but it’s OR
1 Like
@carre It’s OR.
Which makes it easier:/
since the bitwise or of all values in both trees are equal, they must also be equal to the bitwise or of all values in the full tree.
Now cutting each edge corresponds to proper subtree of A. Do a DFS to calculate the number of occurences of bit j in all values in the subtree of all nodes. for each bit that is present in the bitwise OR, check whether it’s also present in the subtree, and that the subtree doesn’t have all of them. If that is valid for all bits, then you have an edge. You can check by counting the occurences in the full tree and the subtree.
3 Likes
Got it. thanks man!