本文主要是介绍1592 C. Bakry and Partitioning，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
有一颗树，问你能不能分成至少2个至多k个连通分量，并且每个连通分量的异或值都相同。
解析
设每个点的异或之和为xo
- 根据异或的性质，如果xo为0，那么说明可以分成两个区间，其两个区间的异或之和一定为0。
- 如果xo不为0，我们要分成m个区间，每个区间为xo，如果我们能分成10个区间，那么一定能分成8个区间，因为我们可以选择相邻的三个连通分量构成一个大连通分量，其异或值还是为xo，因此，我们最后分成的奇数个连通分量的最小值是3。
- 现在题目转化成，能不能分成3个连通分量，异或值相同。
- 思路很简单，dfs遍历每个点的所有子树，如果其自身和子树的异或之和为xo，那么就断链并且记录个数cnt++，断链的方式就是给父节点返回0。
- 如果最后cnt>=3 && k>=3 那么表示满足题意。
代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5;
vector<int>g[N];
int r[N];
int xo=0,cnt=0;
void init(int n){xo=0;cnt=0;for(int i=0;i<=n;i++){g[i].clear();}
}
int dfs(int x,int pre){int son=r[x];for(int j:g[x]){if(pre!=j){son^=dfs(j,x);}}if(son==xo){son=0;cnt++;}return son;
}void solve(){int n,m;scanf("%d%d",&n,&m);init(n);for(int i=1;i<=n;i++){scanf("%d",&r[i]);xo=xo^r[i];}for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);g[a].push_back(b);g[b].push_back(a);}dfs(1,1);if((cnt>=3 && m>=3) || xo==0){puts("YES");}else{puts("NO");}
}
int main() {int t ;scanf("%d",&t);while(t--){solve();}return 0;
}
这篇关于1592 C. Bakry and Partitioning的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
