K MUV LUV UNLIMITED Gym 102361K（树上博弈详解！）

题意：两人轮流取叶子，取到根的人获胜
参考博客
本题其实花了很长时间去理解去看，之前真的不是完全明白为什么这样，看了上面的那篇参考博客，我想我应该对博弈题有一点浅薄的认知了。而我自己写的这一篇博客相当于我理解的一个过程，我觉得是写的更加详细了一点，仅供大家参考，说的内容还是很详实的。

思路：打这场训练的时候当时就根据题意推了很久，用的非常笨的方法，利用已知必胜态必败态推导未知必胜态和必败态，草稿纸上推演了很长时间，就是想尽办法把必败态转化。失败了。因为太过于复杂。

下面介绍博客链接的方法，我认为这个大佬讲的真是非常之好，先贴一下。

我们最先考虑的肯定是单链的情况，可以很轻松的看出结论，1、那便是奇数态为必胜，偶数为必败态。这是一个十分简单轻松便可以得出的结论，但这个结论十分重要！是我们推导剩下情况的基础。

对于较为复杂的情况我们可以考虑这样一个事情

假设这棵树有不止一个儿子（也就是说非单链的情况）那么在非一个儿子的那棵子树上，对于每一个儿子，仍然需要解决的是类似于这棵树的问题，也就是说，对于这棵树每一个出现的分支，只需要判断几个儿子是否产生了必胜态，类似于这样。

那么对于每一个分支，我们都可以这样分解，最后问题便转化成了对于每一个分支（从叶子往上第一个分叉）的子节点，是否会出现必胜态也就是说对于每一个分支点是否出现了必败态，因为什么？因为先手的优势就在于此，我们是是否轻松容易的通过先手优势转化为对方的必败态，而我们只要保证自己不是必败态便可以。那么现在出现了一个问题，必败态是什么？根据刚刚单链的推导情况我们就可以看出来，就是当所有这种分支的链为偶数的时候，我们必败，其余我们必胜。

2、所以实际上，那篇博客中的第二种情况是不必去看的，我们只需要转化成判断所有个分支（从叶子往上第一个分叉）长度是否是偶数，如果有一个奇数，那么我们便可以获胜。

综上所述：实际上我们第一种情况甚至都不用去判断，我们坚持的唯一原则就是，判断所有个分支（从叶子往上第一个分叉）长度是否是偶数即可

代码：

int n ;
VI G[N];
int win;
int son[N];
void dfs(int x,int len){
    if(son[x] == 0){
        if(len % 2)win = 1;
        return ;
    }
    if(son[x] == 1){
        for(auto y : G[x]){
            dfs( y ,len + 1);
        }
    }
    else{
        for(auto y : G[x]){
            dfs( y , 1);
        }
    }
}

int main(){
    int _;
    for(scanf("%d" , &_); _ ; _--){
        scanf("%d" ,&n);
        win = 0;
        for(int i = 1; i <= n ; i ++)son[i] = 0,G[i].clear();
        for(int i = 2; i <= n; i ++){
            int x;
            scanf("%d", &x);
            G[x].pb(i);
            son[x] ++;
        }
        dfs(1,1);
        if(win) puts("Takeru");
        else puts("Meiya");
    }

    return 0;
}