HDU6324 Problem F. Grab The Tree(2018HDU多校联赛第三场，博弈)

本文主要是介绍HDU6324 Problem F. Grab The Tree(2018HDU多校联赛第三场，博弈)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

Little Q and Little T are playing a game on a tree. There are n vertices on the tree, labeled by 1,2,…,n, connected by n−1 bidirectional edges. The i-th vertex has the value of wi.
In this game, Little Q needs to grab some vertices on the tree. He can select any number of vertices to grab, but he is not allowed to grab both vertices that are adjacent on the tree. That is, if there is an edge between x and y, he can’t grab both x and y. After Q’s move, Little T will grab all of the rest vertices. So when the game finishes, every vertex will be occupied by either Q or T.
The final score of each player is the bitwise XOR sum of his choosen vertices’ value. The one who has the higher score will win the game. It is also possible for the game to end in a draw. Assume they all will play optimally, please write a program to predict the result.

Input

The first line of the input contains an integer T(1≤T≤20), denoting the number of test cases.
In each test case, there is one integer n(1≤n≤100000) in the first line, denoting the number of vertices.
In the next line, there are n integers w1,w2,…,wn(1≤wi≤109), denoting the value of each vertex.
For the next n−1 lines, each line contains two integers u and v, denoting a bidirectional edge between vertex u and v.

Output

For each test case, print a single line containing a word, denoting the result. If Q wins, please print Q. If T wins, please print T. And if the game ends in a draw, please print D.

Sample Input

Sample Output

思路

给你一个有n个节点的树,树上的每一个点都有一个权值，然后有Q和T两个人做游戏，Q是先手，他可以挑选任意个不相邻的点，它的得分为这些不相邻的点的异或和，记为A,第二个人T必须选完剩下的树上的所有点，记异或和为B,游戏的获胜者是他们之间得分较大的，让你输出得分较大的。

首先我们计算出这棵树上所有点的异或和，记为sum,当sum==0的时候根据异或的性质证明A=B，那么游戏一定平局
当sum!=0那么先手一定可以找到sum的二进制位上的最高位的那个点，把那个点拿走，那么当第二个人无论怎么取，异或和都不可能比他大，所以必败

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
int main()
{int t,n,u,v,x;scanf("%d",&t);while(t--){int xor_sum=0;scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d",&x);xor_sum^=x;}for(int i=1; i<=n-1; i++)scanf("%d%d",&u,&v);puts(xor_sum?"Q":"D");}return 0;
}