SSLOJ 1441.矿物运输【博弈论】

---

题目：

传送门

---

题意：

给出一棵树以及每个节点的权值，我们在每次操作时都要选择一个节点，将$ta$ta的权值向父节点转移至少一点
现在有两个人用如此操作，当无法继续操作时即是输，问是先手胜还是后手胜

---

分析：

---

代码：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#define LL long long 
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
int a[200005];
struct node{
	int to,next;
}e[400005];
int ls[400005],cnt=0;
void add(int x,int y)
{
	e[cnt]=(node){y,ls[x]};
	ls[x]=cnt++;
	return;
}
int dep[200005];
void dfs(int u,int fa,int d)
{
	dep[u]=d;
	for(int i=ls[u];~i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u,d+1);
	}
	return;
}
int main()
{
	int q=read();
	while(q--)
	{
		int n=read();
		cnt=0;memset(ls,-1,sizeof(ls));
		for(int i=2;i<=n;i++)
		{
			int x=read()+1;
			add(x,i);add(i,x);
		}
		for(int i=1;i<=n;i++) a[i]=read();
		dfs(1,0,0);
		int b=0;
		for(int i=2;i<=n;i++) if(dep[i]&1) b^=a[i];
		if(b) printf("win\n"); else printf("lose\n"); 
	}
	return 0;
}