2019ccpc秦皇岛赛区K. MUV LUV UNLIMITED(博弈)

54 阅读 0 评论 36 点赞

我是靠谱客的博主故意航空，最近开发中收集的这篇文章主要介绍2019ccpc秦皇岛赛区K. MUV LUV UNLIMITED(博弈)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目连接

题意：两个人在一棵树上玩游戏，两人轮流在树上选择一个以上的叶子进行删除。最后删掉根节点的人获胜，问是先手必胜还是后手必胜

(1).若只有一条链，则直接判奇偶（废话）
(2).若不只一条链，则分以下两类情况讨论。

若一个叶子节点的父亲节点不只一个儿子，那么先手必胜。因为删掉这个叶子后若达到必败态那么必胜，若达到必胜态，那么可以再删掉一些叶子节点达到必败态。因为删掉这个叶子节点后，总的叶子节点减少，所以对手无法按照模仿你的策略来进行游戏对抗（感性认识下）
若叶子节点到其最近出度大于1的父亲的链的长度均为偶数，则先手必败，否则先手必胜。由1.得，若存在链长为1的叶子，那么此时必胜。所以我们需要让对手转化为有链长为1的状态。那么我们可以将所有奇数链长转换为偶数链长，这样迫使对方让某一链长减少，使得到达j己方必胜局面。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6+5;
vector<int>V[maxn];
int T;
int n;
int fa[maxn];
bool dfs(int u,int pre){
bool left = 1;
for(int i=0;i<V[u].size();i++){
int v = V[u][i];
if(v==pre)continue;
fa[v]=u;left = 0;
if(dfs(v,u))return 1;
}
if(left){
int tmp = u;
int cnt = 0 ;
while(tmp!=1){
tmp = fa[tmp];cnt++;
if(V[tmp].size()>1){
if(cnt&1)return 1;
else return 0;
}
}
if(tmp==1)return !(cnt&1);//只有一条链的情况 
}
return 0;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=2;i<=n;i++){
int x;scanf("%d",&x);
V[x].push_back(i);
}
puts(dfs(1,0)?"Takeru":"Meiya");
for(int i=1;i<=n;i++)V[i].clear();
}
return 0;
}