codeforces div2-746 C题

题目

题意: 给定n个点的无根树，每个点具有点权a[i]，删除至少1条、至多k-1条边，使得所有连通分量的异或和为0. **分析:如果所有点的异或和为0，肯定可以。仔细研究发现只需要判断分成两个连通分量和三个的情况。因为每个连通分量的异或和相等，任意两个连通分量就可以合并，合并之后其余部分异或和不变。分成两个简单，只要所有点的异或和tot = 0.分成三个难一点，不难发现这三个连通分量都是tot,这样才满足三个连通分量的异或和异或以后是tot，符合所有点的异或和为tot。 ** 解法: dfs，把每个点的所有子树遍历完以后再判断是否异或和为0，如果遍历了一半，其余部分不能保证异或和是0，而且不能再和其他部分连了。 时间复杂度:O(n + m) 代码:

// Problem: C. Bakry and Partitioning
// Contest: Codeforces - Codeforces Round #746 (Div. 2)
// URL: https://codeforces.com/contest/1592/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i