正文
【HDOJ5996】dingyeye loves stone（Nim游戏）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题意：dingyeye喜欢和你玩石子游戏。dingyeye有一棵n个节点的有根树，节点编号为0到n−1，根为0号节点。
游戏开始时，第i个节点上有a[i]个石子。两位玩家轮流操作，每次操作玩家可以选择一个节点，并将该节点上的一些石子（个数不能为0）移动到它的父亲节点上去。
如果轮到某位玩家时，该玩家没有任何合法的操作可以执行，则判负。你在游戏中执先手，你想知道当前局面你能否必胜。
n<=1e5，0<=a[i]<=134217728
思路：
设根节点的深度为0，将所有深度为奇数的节点的石子数目xor起来，则先手必胜当且仅当这个xor和不为0。 证明同阶梯博弈。
对于偶深度的点上的石子，若对手移动它们，则可模仿操作；对于奇深度上的石子，移动一次即进入偶深度的点。 时空复杂度O(n)。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
#define N 110000
#define oo 10000000
#define MOD 1000000007 int dep[N]; int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
int n;
scanf("%d",&n);
dep[]=;
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
x++;
dep[i]=dep[x]+;
}
int ans=;
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
if(dep[i]&) ans^=x;
}
if(ans) printf("win\n");
else printf("lose\n");
}
return ;
}
