[数据结构与算法]【CF1592C】C. Bakry and Partitioning（异或）

烘焙和分割

题意：

• 给定一颗树，树中每个节点都有一个 value 值。再给一个 K ，要求你至少删除树中 1 条边，最多删 K - 1 条边，使得对于删除后的森林，每个连通块内部点 value 异或的值相同。

思路：

分情况讨论：

1. 所有点异或值为零

• 显然这种情况下，根据异或性质，我们任意删一条边，边两端连通块的异或值都相同。所以是 YES。

2. 所有点异或值不为零，假设为 X

• 不为零我们就得探讨下。首先不切不行，至少切一条边。只切一条边的话，要保证两块异或相同，那异或总值只能为 0，矛盾。

• 那切两条边呢？根据异或性质，两个异或值都为 X 的连通块，一定可以融合得到异或值为 0，0 与任何数异或结果都是那个数，也就是说 三个异或值都为 X 的连通块融合起来异或值也是 X。

• 那这样任意三块就能融合成一块，推导下来，我们只需要找三块就行，找五块、七块都是多余的。

• 那 三块 的话，我们就得至少切 两条边，所以 K == 2 时，NO。

• 除此之外，我们 dfs 去搜索一下，是否有两个连通块的异或值为 X。

• 若有两个，剩下那个也肯定是 X，答案就是 YES，否则搜不到就是 NO。

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define rfor(a,b,c) for(int a=b;a>=c;a--)
#define all(a) a.begin(),a.end()
#define oper(a) (operator<(const a& ee)const)
#define endl "\n"
using namespace std;
 
typedef long long ll;
typedef pair<int, int> PII;
 
double DNF = 1e17;
const int N = 100010, M = 200010, MM = 110;
int INF = 0x3f3f3f3f, mod = 1e9 + 7;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D, K;
int a[N];
 
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
int tt, temp;
int dfs_xor(int x, int fa) {
	int cnt = a[x];
	for (int i = h[x]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == fa)continue;
		cnt ^= dfs_xor(j, x);
	}
	if (cnt == temp) { //找到一块就重置
		tt++, cnt = 0;
	}
	return cnt;
}
 
void solve() {
	cin >> n >> k;
 
	temp = 0;
	forr(i, 1, n)h[i] = -1, cin >> a[i], temp ^= a[i];
	idx = 0;
 
	forr(i, 2, n) {
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);
	}
 
	if (temp == 0)cout << "YES\n";
	else {
		if (k == 2)cout << "NO\n";
		else {
			tt = 0;
			dfs_xor(1, -1);
			if (tt > 1)cout << "YES\n";
			else cout << "NO\n";
		}
	}	
}
 
int main() {
	cinios;
 
	cin >> T;
	while (T--)solve();
 
	return 0;
}
/*
*/