题目链接在这里：Problem – K – Codeforces
这题是一道很好的树上博弈的题目，关于博弈论的问题，要先从简单的特殊情况入手，找到一些必胜或者必败的局面，再慢慢推到复杂的情况。因为复杂的状态都是由简单的状态叠加起来的。
关于此题的题解可以看这个博客：(7条消息) MUV LUV UNLIMITED（树上博弈 奇偶性）_jkchen’s Haven-CSDN博客
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=2e6+5; 4 int t,n; 5 int tot,head[MAX],adj[MAX],nxt[MAX],son[MAX]; 6 bool flag,ff[MAX]; 7 void addedge(int u,int v){ 8 tot++; 9 adj[tot]=v; 10 nxt[tot]=head[u]; 11 head[u]=tot; 12 } 13 void dfs(int x,int deep){ 14 //cout<<x<<endl; 15 int i,j,zt=0; 16 if (x==1){ 17 if (son[x]==1) deep++; 18 if ((deep-1)%2==1) flag=false; 19 return; 20 } 21 if (son[x]>1){ 22 if ((deep-1)%2==1) flag=false; 23 return; 24 } 25 dfs(adj[head[x]],deep+1); 26 } 27 int main(){ 28 freopen ("k.in","r",stdin); 29 freopen ("k.out","w",stdout); 30 int i,j; 31 scanf("%d",&t); 32 while (t--){ 33 scanf("%d",&n);tot=0; 34 for (i=1;i<=n;i++) son[i]=head[i]=0; 35 for (i=2;i<=n;i++){ 36 scanf("%d",&j); 37 addedge(i,j); 38 //cout<<i<<"-->"<<j<<endl; 39 son[j]++; 40 } 41 flag=true; 42 for (i=1;i<=n;i++) 43 if (son[i]==0) 44 dfs(i,1); 45 if (flag) printf("Meiya "); 46 else printf("Takeru "); 47 } 48 return 0; 49 }