比赛链接：Codeforces Round #746 (Div. 2)

AB

题就不说了，签到。

A题提交 B题提交

C

假设所有节点的异或和为tot，那么有两种情况

• tot = 0，那么此时一定可以被分成两份。
• tot != 0，那么假设可以分成k份，那么最终分出来的每一块异或和就是tot，并且相邻的三份tot可以合为一份tot，异或和不变，最后只剩下3份tot。

针对tot不等于0的情况，我们只需要搜出来3份tot就可以了。

Walk_Alone 学长提出了一个只用dfs一遍的方法：如果子树已经是tot了，那么就不用将子树合并入父节点了，我的代码就是用这个思路写的。

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        if(ch=='-') f=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}

const int N=1e5+5;

struct edge{
    int to;
    int nxt;
}edg[N<<1];

int head[N],cnt;

inline void add(int u,int v){
    edg[++cnt].to=v;
    edg[cnt].nxt=head[u];
    head[u]=cnt;
}

int t,n,k;

int a[N];

int tot;
int num[N];
int qaq;

inline void init(){
    pd=1;
    qaq=0;
    ohhh=0;
    n=0;k=0;
    memset(a,0,sizeof a);
    memset(num,0,sizeof num);
    memset(head,0,sizeof head);
    cnt=0;
    delu=0,delv=0,tot=0;
}



void dfs1(int now,int fa){
    for(int i=head[now];i;i=edg[i].nxt){
        int to=edg[i].to;
        if(to==fa) continue;
        
        dfs1(to,now);

        if(num[to]==tot)
            qaq++;
        else num[now]^=num[to];
    }
}



int main(){
    t=read();
    while(t--){
        init();
        n=read();k=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),num[i]=a[i];
        for(int i=1;i<n;i++){
            int u,v;
            u=read();v=read();
            add(u,v);
            add(v,u);
        }
        for(int i=1;i<=n;i++)
            tot^=a[i];
        if(tot==0){
            cout<<"YES"<<endl;
            continue;
        }

        dfs1(1,0);

        if(k<=2){
            cout<<"NO"<<endl;
            continue;
        }
        if(qaq>=2){
            cout<<"YES"<<endl;
            continue;
        }
        cout<<"NO"<<endl;
    }
    return 0;
}