bakry专题

1592 C. Bakry and Partitioning

题意 有一颗树,问你能不能分成至少2个至多k个连通分量,并且每个连通分量的异或值都相同。 解析 设每个点的异或之和为xo 根据异或的性质,如果xo为0,那么说明可以分成两个区间,其两个区间的异或之和一定为0。如果xo不为0,我们要分成m个区间,每个区间为xo,如果我们能分成10个区间,那么一定能分成8个区间,因为我们可以选择相邻的三个连通分量构成一个大连通分量,其异或值还是为xo,因此,我