掉分快乐qwq
/* * @Author: Nan97 * @Date: 2021-10-04 22:37:18 * @Last Modified by: Nan97 * @Last Modified time: 2021-10-04 22:49:02 */ #include <iostream> #include <cstring> #define rep(i, b, s) for(register int i = (b); i <= (s); ++i) #define pre(i, b, s) for(register int i = (b); i >= (s); --i) using namespace std; const int N = 1e5 + 10, M = N << 1; int a[N], e[M], ne[M], h[N], idx, xx[N]; int n, k, xo; int cnt; inline void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } inline void out(bool flag); int dfs(int u, int fa) { int res = a[u]; for(int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(j == fa) continue; int t = dfs(j, u); if(t == xo) cnt ++; //如果是异或和xor 我们就 _可以_ 剪掉 else res ^= t; //否则不可以 } return res; } inline void solve() { // 题目分析 /* *对于分割的每一个子树的异或和都为一个相同的值 假设为res *假设树中全部节点的异或和为xor *我们现在想一个式子 假设 a^b^c = x && a = b = c 我们可以推出 a = b = c = x *可以扩展到>=3个数字的异或 *那么对于2个数字,a^b = x && a = b 那么只有一种可能 x = 0 *因此题目可以分类讨论一下 如果k=2 也就是只能分割k-1=1次 *此时只有xor = 0 的时候成,并且一定成立 *k>2 *所以这个树要分为几段异或和均为xor的子树 *肯定是奇数段 因为偶数段xor肯定为0 属于上面的那种情况内 *我们再看这么一个式子, a ^ a ^ a = a 此式显然成立 *上式可以推广到奇数个a的异或和为a *上式意义何在? 只要结果异或和为xor的子树超过1个(一定为奇数) 那么肯定可以合并为3个 *并且k>2 (k的另一层含义为分为 k 个部分,和割k-1次意义相同) *因此我们只需要找到除根节点外的子树异或和为xor的个数 >1 即可 */ idx = 0, xo = 0, cnt = 0; cin >> n >> k; memset(h, -1, sizeof h[0] * (n + 1)); rep(i, 1, n) { cin >> a[i]; xo ^= a[i]; } rep(i, 1, n - 1) { int u, v; cin >> u >> v; add(u, v); add(v, u); } if(!xo) { out(1); return; } dfs(1, -1); if(k <= 2) out(0); else out(cnt > 1); } signed main() { int T = 1; cin >> T; while(T -- ) { solve(); } return 0; } inline void out(bool flag) { if(flag) puts("YES"); else puts("NO"); }