题意

一颗树，两人游戏，每人可选任意个叶子结点删去，最后无法操作的输，问先手必败还是必胜

题解

设一颗树为 X X X ，现在，在其一个非叶子结点添加一个结点，形成树 Y Y Y
若 X X X 为必胜态，则先取刚刚加上的结点，再按照必胜的方式操作，所以 Y Y Y 必胜
若 X X X 为必败态，则只取刚刚加上的结点，留给对手一个必败态，所以 Y Y Y 必胜
发现，只要一个非叶子结点，链接有一个叶子结点，则为必胜态
所以，删点时，删到上述状态，就已经确定了
对每一个叶子结点，计算出向上删到第一个分叉点，需要删的步数
问题就转化为，一堆石子，每人可选任意堆，取走一个，先把某一堆取完的必败
假设石子为 a 1 , a 2 , a 3 , . . . , a n a_1,a_2,a_3,...,a_n a1​,a2​,a3​,...,an​
最后一定是取成 1 , 1 , 1 , . . . , 1 1,1,1,...,1 1,1,1,...,1 后，再取的人必败
所以问题转化为对于石子 a 1 − 1 , a 2 − 1 , a 3 − 1 , . . . , a n − 1 a_1-1,a_2-1,a_3-1,...,a_n-1 a1​−1,a2​−1,a3​−1,...,an​−1 先取完的必胜
全是偶数的一定是必败态
因为，后手重复先手的操作，最后一定是后手先取完
那么，只要有奇数就是必胜态，以为先手可以把它变为全是偶数，留给对手一个必败态
问题解决

代码

#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef  pair<int,int> pp;
vector<int> a[N];
int sz[N],fg;
void dfs(int x,int fa,int d,int la){
    if (sz[x]==1){
        if ((d-la)%2==1) {
            fg=1;
            return;
        }
    }else
    for(auto i:a[x]) if (i!=fa){
        dfs(i,x,d+1,sz[x]==2?la:d);
        if (fg) return;
    }
}

int main(){
    int T;
    sc(T);
    while(T--){
        int n;
        sc(n);
        for(int i=1;i<=n;i++) a[i].cl(),sz[i]=0;
        for(int i=2;i<=n;i++){
            int x; sc(x);
            a[i].pb(x),a[x].pb(i);
            sz[i]++;sz[x]++;
        }
        fg=0;
        a[1].pb(-1);sz[1]++;
        dfs(1,-1,1,0);
        if (fg) puts("Takeru");else puts("Meiya");
    }
    return 0;
}