2018HDU多校3-Problem F. Grab The Tree(hdu 6324)-博弈

题意：

Q和T两人玩游戏，Q先手，从一棵树中选择若干个点，并得到这些点的异或和，要求不能同时选取相邻的两点。Q选完后，T取剩余的点，谁取的这些点的异或和大谁获胜，问比赛结果

思路：

看到两人玩游戏，看到先后手，考虑博弈。
分两种情况讨论，Q=T时，则两人所取点的异或和相同，由异或运算法则可得，Q^T=0，即所有点的异或和为0
Q!=T时，因为Q是先手取，T只能选Q剩下的点，所以Q按照某一规则取点，若异或和大，则就这么取，反之，取相反的一组点，所以Q一定能获胜
其他方法：树形dp

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+100;
int t,n,sum = 0;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int temp;
        sum = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d",&temp);
            sum ^= temp;
        }
        int v,u;
        for(int i = 1; i < n; i++){
            scanf("%d%d",&v,&u);
        }
        if(sum == 0) printf("D\n");
        else printf("Q\n");
    }
    return 0;
}