#NIM博弈#[nssl 1441] 矿物运输

题目

---

解题思路

首先，这是NIM博弈。
我们可以手推初始情况，将所有情况异或起来(除了根节点)，根据是否等于0判断，有$80$80分。
实际我们只需要将层数为奇数的异或起来就可以了。

---

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{int y,next;}a[400010];
int n,T,tot,head[200001],w[200001],ans; 
void add(int x,int y){a[++tot]=(node){y,head[x]};head[x]=tot;}
void dfs(int x,int fa,int dep){
	if (dep==1) ans^=w[x]; 
	for(int i=head[x];i;i=a[i].next){
		int y=a[i].y; 
		if (y==fa) continue; 
		dfs(y,x,(dep==1?0:1)); 
		
	}
}
int main(){
	scanf("%d",&T); 
	while(T--){
		scanf("%d",&n); 
		memset(head,0,sizeof(head)); 
		tot=ans=0; 
		for(int i=1,y;i<n;i++) scanf("%d",&y),add(i+1,y+1),add(y+1,i+1); 
		for(int i=1;i<=n;i++) scanf("%d",&w[i]); 
		dfs(1,0,0); 
		if (ans>0) printf("win\n"); else printf("lose\n"); 
	}
}