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

题解

首先，如果每个部分的XOR都相同（设为X），那么所有节点的XOR要么是X要么是0。

我们先考虑所有节点的XOR是0的情况。这种情况显然是YES，因为我们只需要选择任意一个叶子节点，然后让这个叶子节点独立成一个部分即可。

接着再考虑XOR不是0的情况。
对于这种情况我们首先找到一个尽可能小的子树，使这个子树的XOR等于X。
接着，我们将这个子树删除。此时剩下的树的XOR必然为0。于是我们再在剩下的树中找到一个子树使得其XOR等于X即可。
如果能找到这两个子树，则YES，否则就是NO。

Java

C++