Codeforces Round #746 Div. 2

掉分快乐qwq
C题代码以及分析(在注释里）

/*

 * @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");

}
巴特西

Codeforces Round #746 Div. 2

C题代码以及分析(在注释里）

最新文章

热门文章
