Nim游戏拓展 阶梯博弈

题意：有一颗n个节点的树，1号点为根节点，其他点上分别放有若干个石子，两个人轮流操作，每次可以将某个节点上的若干个石子移动到这个节点的父亲上面，无法操作者负，问先手是否必胜。

以0(root)为的深度为1，我们首先发现，0作为root，它上面的石子不管有多少对结果都无法造成影响，故可以视为0，再考察深度为奇数的节点，如果这上面有石子，那么不管alice从这里拿多少石子移到父亲节点上，bob都可以模仿alice的操作，这样的话，这些石子又将放到深度为奇数的节点上，直到root，因此直到所有奇数深度都到root，alice无法操作了，就必败了。因此我们可以把奇数节点都视作0，即消失了，因为对答案没有贡献。
因为偶数层石子谁最后取完，谁就赢得了游戏，这样问题变转化为偶数层的石子做nim游戏。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;

int n;
int deep[maxn];
int a[maxn];

vector<int> son[maxn];

void dfs(int x, int d)
{
    deep[x] = d;
    for(auto it : son[x]) {
        dfs(it, d+1);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(deep, 0,sizeof(deep));
        scanf("%d",&n);
        for(int i = 0;  i< n; i++) son[i].clear();
        for(int i = 1; i <= n-1; i++){
            int f;
            scanf("%d",&f);
            son[f].push_back(i);
        }

        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }

        dfs(0,1);
        int nim = 0;
        for(int i = 1;  i< n; i++){
            if(deep[i] % 2 == 0){
                nim ^= a[i];
            }
        }
        if(nim == 0){
            printf("lose\n");
        }
        else{
            printf("win\n");
        }
    }
 }