Problem F. Grab The Tree HDU - 6324（树形dp+博弈）

Little Q and Little T are playing a game on a tree. There are nn vertices on the tree, labeled by 1,2,…,n1,2,…,n, connected by n−1n−1 bidirectional edges. The ii-th vertex has the value of wiwi.

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 xx and yy, he can’t grab both xx and yy. 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)T(1≤T≤20), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤100000)n(1≤n≤100000) in the first line, denoting the number of vertices.

In the next line, there are nn integers w1,w2,…,wn(1≤wi≤109)w1,w2,…,wn(1≤wi≤109), denoting the value of each vertex.

For the next n−1n−1 lines, each line contains two integers uu and vv, denoting a bidirectional edge between vertex uu and vv.

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

1

3

2 2 2

1 2

1 3

Sample Output

Q

在树上选取点求异或和，Q先选，剩下的点就是T选的了。问最后谁会赢。

树形dp，dp[i][0/1]代表着这个节点选还是不选。

状态转移方程：

dp[u][1]=max(dp[u][1],dp[u][1]^dp[to][0]);

dp[u][0]=max(dp[u][0],max(dp[u][0] ^ dp[to][1],dp[u][0]^dp[to][0]));

树形dp完了之后，选取dp[1][1]和dp[1][0]之间最大的那一个作为Q的得分，剩下的就是T的得分了，然后作比较就好了。

代码如下：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

const int maxx=1e5+100;
struct edge{
	int to,next;
}e[maxx<<1];
int head[maxx<<1];
int a[maxx];
int dp[maxx][2];
int n,tot;
/*-----------事前准备-----------*/
inline void init()
{
	tot=0;
	memset(head,-1,sizeof(head));
	memset(dp,0,sizeof(dp));
}
inline void add(int u,int v)
{
	e[tot].to=v,e[tot].next=head[u],head[u]=tot++;
}
/*---------------dfs--------------*/
inline void dfs(int u,int f)
{
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int to=e[i].to;
		if(to==f) continue;
		dfs(to,u);
		dp[u][1]=max(dp[u][1],dp[u][1]^dp[to][0]);
		dp[u][0]=max(dp[u][0],max(dp[u][0]^dp[to][1],dp[u][0]^dp[to][0]));
	}
	dp[u][1]^=a[u];
}
int main()
{
	int t,l,r;
	scanf("%d",&t);
	while(t--)
	{
		init();
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&l,&r);
			add(l,r);
			add(r,l);
		}
		memset(dp,inf,sizeof(dp));
		dfs(1,0);
		int ant=max(dp[1][0],dp[1][1]);
		int sum=0;
		for(int i=1;i<=n;i++) sum^=a[i];
		sum^=ant;//先把所有节点的值的异或和求出来，再异或上Q的，就是T的。因为^的逆运算就是^.
		if(sum==ant) puts("D");
		else if(sum>ant) puts("T");
		else puts("Q");
	}
	return 0;
}
           

努力加油a啊，(o)/~