树上博弈——从根节点先后走向叶子节点输赢【递归水题】

A在和B玩游戏，游戏规则如下，有一颗含有n个节点的树，开始棋子会在根节点(也就是1号节点)，每人轮流把棋子从一个节点往其子节点移动，谁先不能移动就会输掉比赛。A让B先走，两个人都特别聪明，问A能不能获得胜利 。

开始以为是直接走一条路径判断深度奇偶即可，但后来发现并不简单，因为是两人交替进行，无法判断到达一个节点 时是按谁的意思往那边走，或者说即使知道当前结点是谁在控制，但是并不知道往哪边走是必胜态，或者说即使当前选择某条路径，判断叶子深度奇偶性后得到输赢的可能，但是仍然无法避免在这条路径上未来是否会被对方控制走向对方的必胜态。

因此放弃正向从根节点走的思路，反向考虑结果。
既然从出发点考虑根节点是为止状态，对于每个叶子节点，完全可以根据其深度奇偶性判断如果局势走到该节点谁输谁赢，如深度7则A赢，深度4则B赢。由此向上递归回溯，知道了子节点的输赢，对于一个分支节点，继续判断其分支是由谁控制的，如果当前结点深度为奇数，为B控制，偶数为A控制。那么当B控制时，因为其子节点回应的是一个定局态【必输或必赢】一旦有任意一条路径让B赢，B一定会取任意一条必赢的路径使得当前分支节点成为必胜态的一部分，若没有任何条子节点返回的路径是B必胜的，那么走向当前分支节点，必输，直接向上返回False。同理，若当前分支节点由A控制，A同样会根据子节点反馈的输赢状态选择一个让自己必胜的路径行走。
这样不断取必胜态回溯到根节点即可得到答案。
有叶子节点回溯的思路避免了正向的未定僵局，因为叶子就是必胜态，依次将必胜态回溯转移，从而得到根节点的必胜态。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define LL long long
#define M(a,b) memset(a,b,sizeof a)
using namespace std;
const int maxn=1e5+7;
int t,n;
vector<int>a[maxn];
int dep[maxn],ans;
bool dfs(int x)
{
    if(a[x].size()==0)
    {
        if(dep[x]&1)return true;
        return false;
    }
    if(dep[x]&1)
    {
        for(int i=0; i<a[x].size(); i++)
            if(!dfs(a[x][i]))return false;
        return true;
    }
    else
    {
        for(int i=0; i<a[x].size(); i++)
            if(dfs(a[x][i]))return true;
        return false;
    }
}
int main()
{
    scanf(\"%d\",&t);
    while(t--)
    {
        ans=1;
        M(dep,0);
        dep[1]=1;
        int tmp;
        scanf(\"%d\",&n);
        for(int i=0;i<=n;i++)a[i].clear();
        for(int i=2; i<=n; ++i)
        {
            scanf(\"%d\",&tmp);
            a[tmp].push_back(i);
            dep[i]=dep[tmp]+1;
        }
        printf(\"%s\\n\",dfs(1)?\"YES\":\"NO\");
    }
}
/*
99
6
1 1 3 3 4
5
1 2 2 4
*/