【多校2018#3】HDU6324 Problem F. Grab The Tree

题面在这里

考虑所有点的异或和\(sum\)

如果\(sum=0\),则无论怎么取都是平局

否则考虑\(sum\)二进制下最高的1

如果先手取了任意一个含有这个1的节点,后者一定取不到这个1

那么先手必胜

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
inline char nc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
int res=0,f=1;char ch=nc();
while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
return res*f;
}

int tst,n;
int main(){
tst=red();
while (tst--){
n=red();int sum=0;
for (int i=1;i<=n;i++) sum^=red();
for (int i=1;i<n;i++) red(),red();
puts(sum==0?"D":"Q") ;
}
return 0;
}