CodeForece 746 div2 C Bakry and Partitioning 题解

题目大意

给定一个有 $n$ 个节点的树，每个点有一个权值 $val[i]$，给定 $k$，你可以删除至少 $1$ 个边，至多 $k-1$ 条边，使剩下的每个连通块所包含的点的权值异或之和相同。

题目地址

思路

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

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

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

   如果一张图可以划分成 $2k+1\ (k \ge 2)$ 个异或和相同且为 $x$ 的连通块，那么可以任意选择三个相邻的连通块，让它们合并，从而保持异或和不变，但是整个图变成了 $2k-1$ 个连通块。

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

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

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

如何划分

如果我们能找到一棵子树，它的异或和为 $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) //情况1
        satisNum[now] = 1;
    if(xorSum[now] == 0 && satisNum[now] == 1) //情况2
        satisNum[now] = 2;
    return;
}

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);
    if(satisNum[1] >= 2)
        succ = true;
    if(succ)
        printf("YES\n");
    else
        printf("NO\n");
    return ;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        work();
    }
    return 0;
}