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

题面在这里

​

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

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

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

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

那么先手必胜

​

示例程序：

#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;
}