HDU-6105: 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≤Pi≤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

题意： 两个人将一棵树染色，最初树上没有颜色，Alice每一次操作可以将树上的某个没有颜色的节点涂成白色，Bob的每一次操作可以将树上某个没颜色的节点涂成黑色，并且与这个节点直接连接的其他节点（不管有没有涂色），都会被染成黑色。Bob有k把剪刀，可以将树的边剪断（那么就不会被黑色晕染到了，但还是可以被直接涂色），如果最后所有节点都有颜色了，那么游戏结束。如果树上存在白色的点，那么Alice获胜，否则Bob获胜。输入是n和k，表示节点个数和剪刀数量，接下来输入n-1个数字，表示下标（从1开始）的节点与哪个节点相连。

分析：通过在纸上画点找规律，我们可以发现，一条链上且不考虑剪刀的时候，有且只有两个节点的时候，Bob才会赢，否则其他情况都是Alice赢，那么可以猜想，当树的size为2的时候，我们就将上面的边剪掉，从下到上，保证Bob局部获胜，如果最后树的size仍然大于2，或者size为1，那么Alice获胜。

• 代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
vector<int>V[maxn];
int sz[maxn];
int n, k;
void dfs(int f, int u)
{
    sz[u] = 1;
    for (int i = 0; i < V[u].size(); i++)
    {
        int v = V[u][i];
        if (v == f) continue;
        dfs(u, v);
        sz[u] += sz[v];
    }
    if (k > 0 && sz[u] == 2)
    {
        k--;
        sz[u] = 0;
    }
}
void clr()
{
    for (int i = 0; i <= n; i++)
        V[i].clear();
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &k);
        clr();
        for (int i = 1; i < n; i++)
        {
            int x;
            scanf("%d", &x);
            V[i + 1].push_back(x);
            V[x].push_back(i + 1);
        }
        dfs(0, 1);
        if (sz[1] > 2 || sz[1] == 1) printf("Alice\n");
        else printf("Bob\n");
    }
    return 0;
}