题目大意：

给定一棵树作为棋盘，两个人进行对战，A玩家每次操作为选定一个空点标记白***玩家每次操作为选定一个空点变为黑色，并把与该点直接相连的点同时变为黑色。同时B玩家作为vip，还可以在任意时刻删除任意两点之间的一条连线，共可进行k次操作。现在规定，在棋盘铺满之后，如果棋盘中还有白点，那么A玩家获胜，否则B玩家获胜。A先下，问谁能获胜。

分析：

本开始觉得是博弈论，但是看 ac 的人也不少，所以觉得可能还是思维题。而且粗略看了一下博弈论思想，好像是大部分都是公平对局。但是这个应该算是有 vip 用户的。
官方题解给出的基本结论是：如果 B 玩家可以将棋盘划分成若干个不连通的两个一组的点对，那么应该就可以赢，否则 A 一定有一种办法可以赢得比赛。

A的必胜策略为：

对于一颗子树，如果它不能分割成两个一组的结点对，那么 A 不断取叶子节点的父亲节点。如果可以分割成两个一组的节点对，那么如果存在一个节点它的子节点中有不止一个叶子节点，那么 A 就取它，否则 A 就不断取叶子节点。

策略必胜性说明：

首先，对于一个不能分成若干节点对的树，如果我每取一次叶子节点的父亲，那么我就相当于逼迫 B 去取我留下的那个叶子节点，这样的策略就相当于我通过我的决策而唯一确定下了 B 的每一次动作。同时 A B 的每一回合都可以看成是从树中取出了一个点对，那么因为这个图是不能被分成若干个点对的，所以一定会出现孤立结点，然后 A 先下到这个孤立结点，然后就赢了。

然后再说能被分成若干节点对的树，如果一个节点的子节点有不止一个叶子节点，那么我选它肯定就得到了两个孤立的点，这样 B 就没办法了。如果是每个节点的子节点中叶子节点数都最多只有一个，那我一直取叶子节点，最后 B 也是不得不生成一个结点数为奇数的子树，对这个子树的处理办法参见对不能分割成若干节点对的情况的处理办法。

这样我就得到了一个 B 获胜的充分必要条件：B可以把这棵树通过技能分成若干节点对。

实现过程：

下面问题就变成了，对于一颗给定的树，判定它是否可以通过 K 次切割变成若干个节点对。我只要每次贪心地切掉叶子节点和它的父亲节点，然后不断切割，看是否过程中会出现孤立点对，就可以判断了。代码写的比较简单，每次寻找叶子节点都是遍历一次，这样时间复杂度：O( n2 ) 也是可以过的，但是题解给的是 O(n) 的时间复杂度，应该是按照一种递归的写法，删除叶子节点和叶子节点的父亲后，叶子节点父亲的其他子节点和它的父亲就都变成了叶子节点，再把这些叶子节点用同样的办法删除就能达到理论上 O(n) 的复杂度了，但是我觉得递归调用函数也会变慢，好吧，其实是我懒得写了。

代码：

#include<bits/stdc++.h>
#define maxn 510
using namespace std;

int test,n,k;
//vecter<int>a[maxn];
//bool is_lone[maxn];
int son_num[maxn];//儿子节点的个数
int father[maxn];//父亲节点的标号
int is_del[maxn];

int main()
{
    scanf("%d",&test);
    while(test--)
    {
        memset(is_del,0,sizeof(is_del));
        memset(son_num,0,sizeof(son_num));
        scanf("%d%d",&n,&k);
        int temp_f;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&temp_f);
            son_num[temp_f]++;
            father[i]=temp_f;
        }
        if(n%2==1)
        {
            printf("Alice\n");
            continue;
        }
        if(n/2>k+1)
        {
            printf("Alice\n");
            continue;
        }
        int flag=0;
        for(int j=1;j<=n;j++)
        {
            for(int i=2;i<=n;i++)
            {
                if(son_num[i]==0&&is_del[i]==0)
                {
                    if(is_del[father[i]]==1)
                    {
                        flag=1;break;
                    }
                    is_del[i]=1;
                    is_del[father[i]]=1;
                    son_num[father[father[i]]]--;
                }
            }
            if(flag==1)break;
        }
        for(int i=1;i<=n;i++)
        {
            if(is_del[i]==0)
            {
                flag=1;
                break;
            }
        }
        if(flag==0)printf("Bob\n");
        else printf("Alice\n");

    }

}

总结：

这道题是当时做的第四题，最后也有 200 人过了。感觉做出来的希望也不能说没有。但是当时约完饭太激动了，一直在一边选地方，一边想题，剩下的将近两小时就没有静下心来想，下次绝对不能这样了。不到最后一分钟就不能停！与其分类成博弈论，不如说是思维题，因为他是通过 A 的完美操作而逼迫 B 进行确定的操作，而博弈论我觉得更多的是对于 B 的每种可能的操作，找到 A 的完美操作使得局势一直保持在 A 能赢的状态下。