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

Submission #131080140 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #131082672 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论