Codeforces Round #746 Bakry and Partitioning Solution (Java/C++)

Solution:

First, if the XOR of each component is the same (represent by X), then the XOR of all nodes is either X or 0.

Let us first consider the case where the XOR of all nodes is 0. This situation is obviously YES, because we only need to select any leaf node, and then let this leaf node become a component independently.

Then consider the case where XOR is not 0.
In this case, we first find a subtree as small as possible so that the XOR of this subtree is equal to X.
Next, we delete this subtree. The XOR of the remaining trees must be 0 at this time. So we can find a subtree in the remaining trees so that its XOR is equal to X.
If these two subtrees can be found, it is YES, otherwise it is NO.

Code:

Java

C++