题解：P7864 「EVOI-RD1」摘叶子

· · 题解

对于这种没有明显结论的博弈论题，我们先处理出特殊情况。在从特殊情况推广到一般情况。这也是大部分 OI 题的常规思路。

首先，树是一条链怎么做，经过手模显然在两端取，那么为偶数的时候先手必胜，反之为奇数的时候先手必败。

其次，我们考虑存在一个父节点，该节点存在多个叶子节点的形式，最经典的就是菊花图，那么有：

考虑推广但一般情况，就是将根几点当成树的一部分结构，那么结构因为是公平组合游戏，那么一定是 P 点或者 N 点，若是 P 状态，我们直接把叶子节点全部拿完，如果是 N 状态，我们就只剩下一个叶子节点。但是对于局面来说，先手都是具有操控全的。

最后，我们推广到一般性情况。对于所有的第二种情况，先手都可以操纵，也就是说一个父节点，该节点存在多个叶子节点的情况为必胜态。否则一定存在若干个链使得所有叶子节点都没有兄弟。这样的话我们需要判断的链条的长度，也就是从该叶子节点出发到达的第一个不是只有一个子节点的父节点，也就是直到一种父节点，该节点存在多个叶子节点的情况出现。因此我们计算出所有链的长度，如果存在奇数，先手必胜；如果全是偶数，则后手必胜。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int T,n,fa[MN],dg[MN];

void clear(){
    for(int i=1;i<=n;i++) dg[i]=fa[i]=0;
}

void solve(){
    cin>>n;
    clear();
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        dg[fa[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(dg[i]) continue;
        int pre=fa[i],len=0;
        while(dg[pre]==1){
            pre=fa[pre];
            len++;
        }
        len++;
        if(len&1){
            cout<<1<<'\n';
            return;
        }
    }
    cout<<"0\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}