BestCoder#90dingyeye loves stone

dingyeye喜欢和你玩石子游戏。dingyeye有一棵$n$个节点的有根树，节点编号为$0$到$n?1$，根为$0$号节点。游戏开始时，第$i$个节点上有$a[i]$个石子。两位玩家轮流操作，每次操作玩家可以选择一个节点，并将该节点上的一些石子（个数不能为$0$）移动到它的父亲节点上去。如果轮到某位玩家时，该玩家没有任何合法的操作可以执行，则判负。你在游戏中执先手，你想知道当前局面你能否必胜。

本题有多组数据，第一行为一个非负整数$T$，表示数据组数。对于每组数据，第一行一个整数$n$，表示节点数目。接下来一行为$n?1$个整数$fa[1]?fa[n?1]$，分别描述了除根节点外每个点的父亲。方便起见，保证$0\leq fa[i]\< i$。接下来一行为$n$个非负整数$a[0]?a[n?1]$，分别描述了每个点初始的石子数。保证$0\le a[i]<134217728$。$1\le T\le 100$，$1\le n\le 100000$。保证$n>100$的测试点数目不超过$7$个。

对于每组数据，输出一行，若先手必胜则输出"win"，否则输出"lose"（不含引号）。

2
2
0
1000 1
4
0 1 0
2 3 3 3

win
lose

分析：其实就是个n堆的尼姆博弈。因为是一棵树，所以是分层次的，而且都是连起来的。那么先手当然希望是把1,3,5,7....奇数层的都清空，这样就可以使后手无法满足题目中"并将该节点上的一些石子移动到它的父亲节点上去"，因为层与层都割断了嘛。至于为什么是奇数层，是因为把根节点当做第0层，因为根节点不能移动。

体会：思路还是很清晰的，就是不知道如何处理把奇数层给选出来，当时还用了vector把属于同一根节点的儿子都加进来，其实还是在层次的处理上还是不正确的....

AC代码：

#include <iostream>
#include <cstdio>
#define N 200050using namespace std;int n,fa[N],dep[N];
void solve() {scanf("%d",&n);for (int i=1;i<=n-1;i++) {scanf("%d",&fa[i]);dep[i] = dep[ fa[i] ] + 1;}int ans = 0;for (int i=0;i<=n-1;i++) {int v; scanf("%d",&v);if (dep[i]&1) ans ^= v;}if (!ans) puts("lose"); else puts("win");
}int main()
{int T = 0; scanf("%d",&T);while (T--) solve();return 0;
}