hdu6105 Gameia[博弈]

Problem Description

Alice and Bob are playing a game called ‘Gameia ? Gameia !’. The game goes like this :
\0. There is a tree with all node unpainted initial.
\1. Because Bob is the VIP player, so Bob has K chances to make a small change on the tree any time during the game if he wants, whether before or after Alice’s action. These chances can be used together or separate, changes will happen in a flash. each change is defined as cut an edge on the tree.
\2. Then the game starts, Alice and Bob take turns to paint an unpainted node, Alice go first, and then Bob.
\3. In Alice’s move, she can paint an unpainted node into white color.
\4. In Bob’s move, he can paint an unpainted node into black color, and what’s more, all the other nodes which connects with the node directly will be painted or repainted into black color too, even if they are white color before.
\5. When anybody can’t make a move, the game stop, with all nodes painted of course. If they can find a node with white color, Alice win the game, otherwise Bob.
Given the tree initial, who will win the game if both players play optimally?

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with two integers N and K : the size of the tree and the max small changes that Bob can make.
The next line gives the information of the tree, nodes are marked from 1 to N, node 1 is the root, so the line contains N-1 numbers, the i-th of them give the farther node of the node i+1.

Limits

$T≤100$
$1≤N≤500$
$0≤K≤500$
$1≤P_i≤i$

Output

For each test case output one line denotes the answer.
If Alice can win, output “Alice” , otherwise “Bob”.

Sample Input

2
2 1
1
3 1
1 2

Sample Output

Bob
Alice

题目大意

Bob和Alice玩游戏。

一颗树，期初所有点都没有颜色，Alice先手，可以把一个没有颜色的点染为白色，然后Bob可以把一个点及其周围的点全都染位黑色。如果最后有白色的点剩余，Alice就胜，否则Bob胜。

然后Bob有一堆骚操作，可以在任意时候删掉树的任意条边（总删除的边的条数不超过k）。

给你一个树和k，求最后谁胜

题解

染成黑色的点，可以直接删去。

只有2个点，Bob胜。

Alice如果下叶子节点，Bob就必须下它上面的一个点。所以，如果总的点数位奇数个，显然Alice赢。

如果为偶数个，如果没有完美匹配，必然存在以下两种情况中的一种。1，使最后剩余一个点，与2个及2个以上个叶子节点相连，并且该点上面的点已经被染色。这个时候，Alice染了这个点，就必胜了。2，剩下一个孤点（周围的点都被染色了）。

以上两种情况，Bob删掉树的边，也毫无意义，相当于分多个联通块，每个可以单独处理。

如果有完美匹配，就必然存在一个点，度数为2，且与一个叶子节点相连。染了那个叶子节点，Bob必须把上面那个点染色。这一轮，就有三个点被染为黑色，剩余的空点一定为奇数个，Alice必胜。

所以如果Bob没有操作的情况下，只有在点的个数为2的时候会胜。

Bob只有把完美匹配的数隔成n/2 个部分，使每个部分点的个数为2，才可胜。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
    if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
    while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
    return k*base;
}
void write(int x)
{
    if(x<0){putchar('-');write(-x);}
    else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=500+100;
int T,X,n,k;
int to[maxn<<1],ne[maxn<<1],po[maxn],id;
int bj[maxn];
void add(int x,int y)
{
    id++;to[id]=y;ne[id]=po[x];po[x]=id;
}
void dfs(int x)
{
    for (int i=po[x];i;i=ne[i])
    {
        dfs(to[i]);
        if (!bj[to[i]]&&!bj[x])
        {
            bj[to[i]]=1;
            bj[x]=1;
        }
    }
}
int main()
{
    T=read();
    while (T--)
    {
        n=read();k=read();
        id=0;
        memset(po,0,sizeof(po));
        memset(bj,0,sizeof(bj));
        for (int i=2;i<=n;i++)
        {
            X=read();
            add(X,i);
        }
        int flag=1;
        dfs(1);
        for (int i=1;i<=n;i++)
        {
            if (bj[i]==0) 
            {
                flag=2;
                break;
            }
        }
        if (flag==2)
        {
            printf("Alice\n");
        } else
        {
            if (k>=(n-1)/2) printf("Bob\n"); else
            printf("Alice\n");
        }
    }
    return 0;
}