Codeforces Round #746 (Div. 2)(1592)
本文最后更新于 17 天前,其中的信息可能已经有所发展或是发生改变。

比赛链接: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;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇