I am confused by this problem: 429A - Xor-tree
As far as I understand, in the sample test, after applying operation on node 4, we have:
0 0 1 0 0 0 1 1 1 0
Now, if we apply operation on node 7, we get the original sequence back; that is:
1 0 1 1 0 1 0 1 0 1
So, the upshot is if we apply operations on the nodes that are even distance apart, they completely cancel each other out, leading to only four distinct states.
I am now convinced that I am thinking about the problem in a wrong way. Is it perhaps that the initial node that you are applying the operation to does not flip its state? (I read the problem statement multiple times but it is not written that way)
Could anyone point out what I am missing from the problem statement? Judging from so many AC's I am sure I am missing something but at the moment I stay puzzled. I read the editorial but still could not make sense out of the problem.
Thanks!
You must have figured it out yourself by now but this is for future reference. The problem is talking about Rooted tree. A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. One can read more about Rooted Tree here: (https://en.wikipedia.org/wiki/Tree_(graph_theory))
The problem statement mentions that "The root of the tree is node 1." Hence root number 1 has been designated the root and you have to solve the problem according to that. Now coming back to the sample example.
If we apply the operation to node number 4, it won't affect any other nodes because this node has no son. Same goes for node number 7. By performing operation on these two nodes, we get the desired answer. Hence the answer is 4 and 7.