2017 多校赛6 Gameia hdu 6105_rpnryh6wa3f拢-CSDN博客

本文链接：https://blog.csdn.net/logch/article/details/77093322

题目意思：太长了，自己看吧。
题目思路：这个博弈可以得出一个很重要的结论（神队友分析出来的，很坑的神队友）：如果能把树切割成两两配对的形式则Bob赢，否则Alice赢（网友可以自行验证）。我提供的实现思路（树拓扑），顺便也和另一队友分别做了验证和提供数据。后来想了一下，也可以用二分图最大匹配来做嘛，一棵树能两两匹配当且经当它完美匹配（最大匹配数*2==节点数）。做法多种多样，关键是这个结论的分析过程（多得神坑队友给力，说他神坑是因为他老犯低级错误OrzOrz)。
代码还是贴一下吧（队友主写）。。。

#include <cstring>
#include <cstdio>
#include <iostream>
#include <string>
#include <climits>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
#define MAXN_NUM 0x3f3f3f3f
#define EPS 1e-6

#define DGA(x)
#define DFA(x) 
#define PRT(x,a) printf("%s%d%s\n",a,x,a)
#define TEST(x)  printf("---------test %c---------\n",x+'A')
#define Fin(i,f,t) for(int i=f;i<=t;++i)
#define Fde(i,f,t) for(int i=f;i>=t;--i)
#define SfI(x)  scanf("%d",&x)
#define SfLL(x) scanf("%lld",&x)
#define SfD(x)  scanf("%lf",&x)
#define SfC(x)  scanf("%c",&x)
#define SfS(x)  scanf("%s",x)

#define MAXN 5000

int deg[MAXN]={},far[MAXN]={};//deg树节点的度（儿子数）， far是father的意思，怪题目单词错了。
bool exist[MAXN];//节点是否以删除
int N,K;
bool Judge(){
    if(N%2)//显然奇数节点不可能两两配对
        return false;
    if(K < (N/2-1))
        return false;
       //我不知道队友为什么对这个判断产生疑问，很明显的撒：留下N/2条边，原N-1条边，最少需要（N/2-1）次切割
    memset(exist,true,sizeof exist);
    exist[0] = false;//这里是个坑
    int cnt = N;
    while(cnt){
        Fin(i,1,N) if(!deg[i]){//叶子节点，度数为0
            //printf("%d - %d\n",i,far[i]);
            if(exist[far[i]]){
                --deg[far[far[i]]];//可能产生新的叶子节点
                exist[i] = exist[far[i]] = false;//删点
                deg[i] = deg[far[i]] = -1;//删点
                cnt -= 2;
                break;
            }
            else//如果存在未删除的叶子节点，但是他父亲已经删除了，gg
                return false;
        }
    }
    return true;
}
int main(void){
    DFA(freopen("D:\\test.txt","r",stdin));
    //freopen("D:\\tsst.txt","w",stdout);
    int T;
    SfI(T);
    Fin(t,1,T){
        memset(deg,0,sizeof deg);
        scanf("%d%d",&N,&K);
        Fin(i,2,N){
            SfI(far[i]);
            ++deg[far[i]];
        }
        printf("%s\n",Judge()?"Bob":"Alice");
    }
    return 0;
}