http://acm.hdu.edu.cn/showproblem.php?pid=6105
若树可以通过剪边分为若干个两个节点相连的集合，且k大于等于剪边次数，则Bob赢。剩下的情况皆为Alice赢
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; const int N=505; const int inf=0x3f3f3f3f; int vis[N]; vector<int>v[N]; queue<int>q; void clear(queue<int>& q) { queue<int> empty; swap(empty, q); } int main(){ std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T,n,k,d; cin>>T; while(T--){ cin>>n>>k; for(int i=0;i<=n;i++){ v[i].clear(); vis[i]=0; } clear(q); for(int i=2;i<=n;i++){ cin>>d; v[i].push_back(d); v[d].push_back(i); } for(int i=1;i<=n;i++){ if(v[i].size()==1){ q.push(i); } } int flag=1; while(!q.empty()&&flag){ int num=0,p; int t=q.front(); q.pop(); if(vis[t]) continue; for(int i=0;i<v[t].size();i++){ if(vis[v[t][i]]==0){ num++; p=v[t][i]; } } if(num==1){ vis[t]=1; vis[p]=1; num=0; for(int i=0;i<v[p].size();i++){ if(vis[v[p][i]]==0){ q.push(v[p][i]); } } } else if(num==0) flag=0; else q.push(t); } if(flag==1){ for(int i=1;i<=n;i++){ if(vis[i]==0){ flag=0; } } } if(flag&&k>=n/2-1) cout<<"Bob"<<endl; else cout<<"Alice"<<endl; } return 0; }
