CodeForece 746 div2 C Bakry and Partitioning 题解

题目大意

给定一个有$n$个节点的图，每个点有一个权值$val[i]$，给定$k$，你可以删除 至少$1$个边，至多$k?1$ 条边，使剩下的每个连通块所包含的点的权值异或之和(用$0$去依次异或每个点得到的值)相同。

题目地址

思路

1. 假如整个图的点异或和为$0$，那么显然可以任意删除一条边，分出的两个连通块的点异或之和显然相同。

2. 如果整个图的点异或和不为$0$ ，而为$x$：

   那么首先它不可能被划分成偶数个异或和相同的连通块。

   如果一张图可以划分成$2k+1(k\ge 2)$个异或和相同且为$x$的连通块，

   那么可以任意选择三个相邻的连通块，让它们合并，从而保持异或和不变，但是整个图变成了$2k?1$个连通块。

   也就是说，如果我们能把它划分成3个即以上个奇数个异或和为$x$连通块，那么我们一定可以把它划分成3个连通块。

   即，划分成3个异或和均为$x$的连通块 是 这种情况可以成功划分 的充要条件。

   所以我们如果$k\ge 2$，那么就可以尝试划分，否则就直接NO了。

   那么重点就是在这个划分了。

如何划分

如果我们能找到一棵子树，它的异或和为$x$，且把它删去后，从剩下的树中，也能找到异或和为$x$的子树，那么就可以把树划分成了。

具体来说，我们以$1$号节点为根，dfs整棵树，用$xorSum[i]$记录以$i$号节点为根的子树异或和。用$xorVal$记录整棵树的异或和。

在dfs中，我们用$satisNum[i]$记录以$i$号节点为根的子树中，找到的异或和为$xorVal$的子树个数。那么有以下两种情况

1. 在以一个节点$t$为公共父节点的不同子树，都能找到异或和为为$xorVal$的子树，那么经过dfs后，$satisNum[t]=2$，就能够找到满足题意得内容了
2. 在以一个节点$t$为公共父节点的相同子树上，在更深层找到了异或和为$xorVal$的子树，又在它上面找到了一个节点$s$，$xorSum[s]=0$，那么就说明在它们之间的节点异或和也为$xorVal$。那么此时，$satisNum[t]=2$。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int maxN = 1e5 + 7;int T, n, k, head[maxN], cnt, satisNum[maxN];
long long val[maxN], xorSum[maxN], xorVal;
bool succ;struct Edge {
    int from, to;
}e[maxN << 1];inline void add(int u, int v)
{
    e[++cnt].from = head[u];e[cnt].to = v;head[u] = cnt;
}void dfsXorSum(int now, int fa)
{
    for(int i = head[now]; i; i = e[i].from) {
    int y = e[i].to;if(y == fa)continue;dfsXorSum(y, now);xorSum[now] ^= xorSum[y];satisNum[now] += satisNum[y];if(satisNum[now] > 1) //剪枝，既然已经找到两个了，那么就不用继续找下去了。return;}if(xorSum[now] == xorVal) //情况1satisNum[now] = 1;if(xorSum[now] == 0 && satisNum[now] == 1) //情况2satisNum[now] = 2;return;
}void debug()
{
    printf("%lld\n", xorVal);for(int i = 1; i <= n; ++i)printf("# %d %lld\n", i, xorSum[i]);for(int i = 1; i <= n; ++i)printf("# %d %d\n",i, satisNum[i]);
}inline void work()
{
    succ = false;cnt = 0;memset(head, 0, sizeof head);memset(satisNum, 0, sizeof satisNum);memset(xorSum, 0, sizeof xorSum);scanf("%d%d", &n, &k);for(int i = 1; i <= n; ++i) {
    scanf("%lld", &val[i]);xorSum[i] = val[i];}for(int i = 1; i < n; ++i) {
    int x, y; scanf("%d%d", &x, &y);add(x, y); add(y, x);}xorVal = 0;for(int i = 1; i <= n; ++i)xorVal ^= val[i];if(xorVal == 0) {
    printf("YES\n");return ;}else if(k == 2) {
    printf("NO\n");return ;}dfsXorSum(1, 0);//debug();if(satisNum[1] >= 2)succ = true;if(succ)printf("YES\n");elseprintf("NO\n");return ;
}int main()
{
    scanf("%d", &T);while(T--) {
    work();}return 0;
}