大魚海棠_紀中4637_Trie維護Sg函數值

Description

椿是掌管海棠花的少女，她所在的世界不為人們所知，他們的天空就是人類的海底。生活在那個世界裡的他們不是人，也不是魚，而是其他人，掌管着人間的規律。

按照他們的習俗，在16歲那年，椿變為一條海豚到人間巡禮。在第六天，她被大海中的一張網困住，一個人類男孩因為救她而落入深海死去。為了報恩，她回去後私自一人去了如升樓找到靈婆（死去的好人的靈魂化為一條小魚安放在那裡）。她以自己一半的壽命為代價，與靈婆換得了男孩的靈魂，從此她和男孩性命相連。她必須背着族人将拇指大的小魚養大為比鲸還要大的鲲，并将它放歸人世。

湫是椿的同伴，他得知椿給人類男孩續了命之後非常震驚。一次意外，椿昏睡了很久，湫利用這個機會去了如升樓，要與靈婆進行交易，給椿續命。然而這次靈婆處處為難他，要湫和她打麻将，打赢了才能答應他。

但是出題人并不會打麻将，是以我們來讨論另外一個遊戲……

靈婆給了湫一棵有n 個節點的有根樹（1為根），每個節點初始時都是白色的。湫和靈婆輪流操作（湫先手），每次選擇一個白點，将它到根路徑所有點染黑，誰最後将整棵樹染黑了，誰就輸。

湫沒有爹沒有娘，他一直以來天不怕地不怕，但最害怕的，就是讓椿受苦。他非常希望椿能幸福地生活下去，于是找到了人間的你，希望你來判斷最優政策下，誰會赢得這場遊戲。

Input

題目會有多組資料，第一行一個正整數 cas，表示資料組數。

對于每組資料，開頭一個正整數n ，表示樹的節點個數。

接下來一行n-1 個整數，表示2~n 号節點的父親編号。注意如果n=1 會有空行。

Output

對于每一組資料，如果湫能赢，輸出YES，否則輸出NO。

Sample Input

2

4

1 2 3

5

1 1 2 3

Sample Output

YES

YES

Data Constraint

Analysis

純粹是沖着題目來的

這題其實是[BZOJ4134] ljw 和 lzr 的 hack 比賽（[JZOJ4401]dierti）的弱

化版本，采用原題的方法，使用Trie維護Sg函數值可以做到Ο(nlog2n)。

但是！！！

本題其實是一個簡單的Chomp!遊戲，首先由于這是一個公平組合遊戲，是以一定存在必勝政策。

令先手先選擇根節點，如果後手選擇某個節點之後能必勝，那麼顯然先手可

以第一步就選擇後手所選。是以除非隻有1個點，否則先手必勝。

時間複雜度Ο(1)。其實樹都不需要存下來

代碼

#include <stdio.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,k;
        scanf("%d",&n);
        for (int i=;i<=n-;i++)
            scanf("%d",&k);
        if (n!=)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return ;
}