Problem Description#

dingyeye loves play stone game with you.

dingyeye has an n-point tree.The nodes are numbered from 0 to n−1,while the root is numbered 0.Initially,there are a[i] stones on the i-th node.The game is in turns.When one move,he can choose a node and move some(this number cannot be 0) of the stones on it to its father.One loses the game if he can’t do anything when he moves.

You always move first.You want to know whether you can win the game if you play optimally.

Input#

In the first line, there is an integer $T$ indicating the number of test cases.

In each test case,the first line contains one integer n refers to the number of nodes. The next line contains $n−1$ integers $fa[1]⋯fa[n−1]$,which describe the father of nodes $1⋯n−1$(node 0 is the root).It is guaranteed that $0≤fa[i]<i$. The next line contains n integers $a[0]⋯a[n−1]$,which describe the initial stones on each nodes.It is guaranteed that 0≤a[i]<134217728. $1≤T≤100,1≤n≤100000$.

It is guaranteed that there is at most $7$ test cases such that $n>100$.

Output#

For each test case output one line.If you can win the game,print “win”.Ohterwise,print “lose”.

Sample Input#

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

Sample Output#

win
lose

题目大意#

由叶节点向根移石子
移不了的输

题解#

可看做多个阶梯博弈
将奇数层异或就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int f[100005], a[100005];
vector<int> ch[100005];
int S;
void DFS(int x,int D)
{
    if(D&1) S^=a[x];
    for(auto i:ch[x])
    {
        DFS(i,D+1);
    }
}
int main(int argc, char const *argv[])
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            ch[i].clear();
        for (int i = 1; i <= n - 1; i++)
        {
            scanf("%d", &f[i]);
            ch[f[i]].push_back(i);
        }
        for (int i = 0; i <= n - 1; i++)
        {
            scanf("%d", &a[i]);
        }
        S = 0;
        DFS(0,0);
        if(S)
            printf("win\n");
        else 
            printf("lose\n");
    }
    //while(1);
    return 0;
}