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\ge2\)，那么就可以尝试划分，否则就直接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) //情况1
        satisNum[now] = 1;
    if(xorSum[now] == 0 && satisNum[now] == 1) //情况2
        satisNum[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");
    else
        printf("NO\n");
    return ;
}

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

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/10/11/CodeForece-746-div2-C/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！