Xor 思维题

题目描述

小\(Q\)与小\(T\)正在玩一棵树。这棵树有\(n\)个节点，编号为 \(1\)，\(2\) \(3...n\)，由\(n-1\)条边连接，每个节点有一个权值\(w_i\)。

在这个游戏中，小 \(Q\) 需要选择一些节点。他可以选择任意个数的点（小\(Q\)一定会选择最优策略），但是一条边连接的两个节点不能同时被选。

当小\(Q\)选完后，小\(T\)将选择剩下的节点。这样这棵树上的每个点都将被小\(Q\)或者小\(T\)选择。

最后两人的分数分别为自己选择的点的权值异或和，分数大的一方获胜，当然有可能是平局。

输入格式

第一行一个整数\(T(T \leq 20)\)，表示测试数据组数

接下来\(T\)组，对于每一组，第一行一个整数\(n\)

第二行有\(n\)个整数，为\(w_1,w_2...w_n\)，

接下来\(n-1\)行，每行两个整数\(x\)，\(y\)，表示\(x\)和\(y\)

之间有一条边连接

输出格式

对于每一组，答案只有一行，如果小\(Q\)获胜输出\(Q\)，小\(T\)获胜输出\(T\)，如果平局输出\(D\)。

样例

样例输入

2
3
2 2 2
1 2
1 3
4
7 1 4 2
1 2
1 3
2 4

样例输出

Q
D

样例解释

在第一组中，小\(Q\)选择任意一个节点，分数为\(2\)，小\(T\)选择剩下两个节点，分数为\(0\)，小\(Q\)获胜

在第二组中，小\(Q\)最好只能和小\(T\)平局，所以输出\(D\)
数据范围与提示

对于$30% \(的数据，\)n \leq 20$
对于\(100\%\)的数据，\(n \leq 100000\),\(w_i \leq 10^9\)。

分析

一道不错的思维题

首先我们考虑平局的情况

如果整棵树上所有节点的异或和恰好为\(0\)的话

那么无论先手选走哪一些点，后手选走的点一定与先手选走的点相同，这样才能保证异或和为\(0\)

如果整棵树上所有节点的异或和不为\(0\)，那么我们在二进制位中会找到一个最高位的\(1\)

先手只要把这个\(1\)选走，那么必定可以获胜

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],n;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int tot=0;
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            tot^=a[i];
        }
        for(int i=1;i<n;i++){
            int aa,bb;
            scanf("%d%d",&aa,&bb);
        }
        if(tot==0) printf("D\n");
        else printf("Q\n");
    }
    return 0;
}