Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 143 Accepted Submission(s): 16
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pii pair<int,int> #define pil pair<int,ll> #define mkp make_pair const int INF=0x3f3f3f3f; const ll inf=1e18; const int maxn=1e6+10; int siz[maxn],fa[maxn],cnt[maxn]; int T,n,m; vector<int> vec; struct Edge{ int v,nxt; } edge[maxn<<1]; int head[maxn],tot; void Init() { tot=0; fa[1]=-1; for(int i=0;i<=n;++i) head[i]=-1,cnt[i]=0; vec.clear(); } void AddEdge(int x,int y) { edge[tot].v=y; edge[tot].nxt=head[x]; head[x]=tot++; } void dfs(int u) { for(int i=head[u];~i;i=edge[i].nxt) { int v=edge[i].v; if(v==fa[u]) continue; fa[v]=u; dfs(v); } } int main() { scanf("%d",&T) ; while(T--) { scanf("%d",&n); Init(); for(int i=2;i<=n;++i) { int x; scanf("%d",&x); cnt[x]++;cnt[i]++; AddEdge(i,x);AddEdge(x,i); } dfs(1); cnt[1]++; for(int i=1;i<=n;++i) if(cnt[i]==1) vec.push_back(i); int flag=0; for(int i=0,len=vec.size();i<len;++i) { int v=vec[i]; if(cnt[fa[v]]>2) {flag=1;break;} int res=1; while(cnt[fa[v]]==2) { v=fa[v]; res++; } if(res&1) flag=1; } if(flag==1) puts("Takeru"); else puts("Meiya"); } return 0; }
2019CCPC秦皇岛 K MUV LUV UNLIMITED(博弈)
原文:https://www.cnblogs.com/songorz/p/11604529.html