题目链接
Problem - 1592C - Codeforces
题目大意
给你一棵最小生成树 每个节点有一个值 两个节点联合的值等于两个节点xor
你可以将这一颗树的边进行截断
让这棵树最终分为最多k部分 最小2部分
能让这些部分的值相等 输出yes否则no
题目思路
这是一个最小生成树上搜索的题 但是他每个节点的值计算却应用了位异或 所以我们从这里切入进行思考
很容易发现所有节点都xor起来之后的结果 设为tot 这个tot也一定等于分成的那些部分的值
tot
如果为0意味着
一定至少有两块相等的部分异或 这也就满足了条件中的至少将树分成两部分且两部分的值相等
直接输出yes
如果不为0意味着
不能分成两部分相等 至少要是三部分相等才可满足题意 那么就进行书上搜索判断有多少部分等于这个tot 若这个部分大于3个即满足题意 这个部分数量不可能是偶数个 不然就会导致最后的tot为0
所以一定是奇数个
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,T,k;
int a[maxn];
int dp[maxn];
vector<int >v[maxn];
int tot;
int ans;
int dfs(int now,int fa)
{int x=now;int tmp=a[x];for(int i=0;i<v[x].size();i++){int y=v[x][i];if(y==fa)continue;tmp^=dfs(y,x);} if(tmp==tot){ans++;return 0;}return tmp;
}
int main()
{cin>>T;while(T--){scanf("%d %d",&n,&k);tot=0;ans=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);tot^=a[i]; v[i].clear();} int x,y;for(int i=1;i<=n-1;i++){scanf("%d %d",&x,&y);v[x].push_back(y);v[y].push_back(x);} if(tot==0){cout<<"YES"<<endl;continue;}dfs(1,0);//cout<<tot<<" "<<ans<<endl;if(k>=3&&ans>=3){cout<<"YES"<<endl;continue;}cout<<"NO"<<endl;}return 0;
}