题目意思:太长了,自己看吧。
题目思路:这个博弈可以得出一个很重要的结论(神队友分析出来的,很坑的神队友):如果能把树切割成两两配对的形式则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;
}
这个题目对我们这种渣渣来说算难题了,能写出来算侥幸Orz。。