Poachers

题意翻译

**原文直译（简要翻译在后面）** Alice 和 Bob 是两个在森林里砍树的人。 一个森林一个是由零个或多棵树构成的集合。一棵树是没有环的连通图。一颗有根树有一个特别的叫做根的节点。定义点 $v$ 的父节点是在根到点 $v$ 的路径上里点 $v$ 最近的一个点。点 $v$ 的子节点是以点 $v$ 为父节点的节点们。我们称一个点是叶子当且仅当它没有子节点。 在这个问题中，我们定义一个点的深度为这个点到根的简单路径上包含的点的数量，这棵树的秩是它深度最小的那个叶子的深度。 初始时这里有一个有根森林，Alice 和 Bob 在这个森林上玩游戏。他们交替进行决策，其中 Alice 为先手，Bob 为后手。在他们的回合开始的时候，该玩家选择森林中的一颗树，然后选择一个正的「裁剪深度」，它不应该超过这棵树的秩。然后他将深度不超过「裁剪深度」的点移除，其他点变成一些树。一个连通块所代表的树的新的根为，在本次删点之前，深度最小的点。然后它们会加入森林，然后游戏继续。 当轮到某位玩家进行操作时，森林为空，那么他就输了。 问你当两人都采用最优策略时，谁会赢。 **简要翻译** 给你一个森林，两人轮流操作，每次选一棵树，然后选一个不超过这棵树的秩的正整数 $d$，将深度不超过 $d$ 的点删去，保留其他点在森林中。Alice 为先手，Bob 为后手，无法操作者输。若两人均采用最优策略，谁能赢？ 这棵树的秩是它深度最小的那个叶子的深度。

题目描述

Alice and Bob are two poachers who cut trees in a forest. A forest is a set of zero or more trees. A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a node $ v $ is the next vertex on the shortest path from $ v $ to the root. Children of vertex $ v $ are all nodes for which $ v $ is the parent. A vertex is a leaf if it has no children. In this problem we define the depth of vertex as number of vertices on the simple path from this vertex to the root. The rank of a tree is the minimum depth among its leaves. Initially there is a forest of rooted trees. Alice and Bob play a game on this forest. They play alternating turns with Alice going first. At the beginning of their turn, the player chooses a tree from the forest. Then the player chooses a positive cutting depth, which should not exceed the rank of the chosen tree. Then the player removes all vertices of that tree whose depth is less that or equal to the cutting depth. All other vertices of the tree form a set of rooted trees with root being the vertex with the smallest depth before the cut. All these trees are included in the game forest and the game continues. A player loses if the forest is empty at the beginning of his move. You are to determine whether Alice wins the game if both players play optimally.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 5 \cdot 10^5 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ ) — total number of vertices in the initial forest. The second line contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 0 \leq p_i \leq n $ ) — description of the forest. If $ p_i = 0 $ , then the $ i $ -th vertex is the root of a tree, otherwise $ p_i $ is the parent of the vertex $ i $ . It's guaranteed that $ p $ defines a correct forest of rooted trees. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

输出格式

For each test case, print "YES" (without quotes) if Alice wins, otherwise print "NO" (without quotes). You can print each letter in any case (upper or lower).

输入输出样例

输入样例 #1

4
4
0 1 0 3
7
0 1 2 0 4 5 6
4
0 1 1 2
7
0 1 1 2 2 3 3

输出样例 #1

NO
YES
NO
YES

说明

In the first test case Bob has a symmetric strategy, so Alice cannot win.  In the second test case Alice can choose the second tree and cutting depth $ 1 $ to get a forest on which she has a symmetric strategy.  In third test case the rank of the only tree is $ 2 $ and both possible moves for Alice result in a loss. Bob either can make the forest with a symmetric strategy for himself, or clear the forest.  In the fourth test case all leafs have the same depth, so Alice can clear the forest in one move. 

题意翻译

**原文直译（简要翻译在后面）** Alice 和 Bob 是两个在森林里砍树的人。 一个森林一个是由零个或多棵树构成的集合。一棵树是没有环的连通图。一颗有根树有一个特别的叫做根的节点。定义点 $v$ 的父节点是在根到点 $v$ 的路径上里点 $v$ 最近的一个点。点 $v$ 的子节点是以点 $v$ 为父节点的节点们。我们称一个点是叶子当且仅当它没有子节点。 在这个问题中，我们定义一个点的深度为这个点到根的简单路径上包含的点的数量，这棵树的秩是它深度最小的那个叶子的深度。 初始时这里有一个有根森林，Alice 和 Bob 在这个森林上玩游戏。他们交替进行决策，其中 Alice 为先手，Bob 为后手。在他们的回合开始的时候，该玩家选择森林中的一颗树，然后选择一个正的「裁剪深度」，它不应该超过这棵树的秩。然后他将深度不超过「裁剪深度」的点移除，其他点变成一些树。一个连通块所代表的树的新的根为，在本次删点之前，深度最小的点。然后它们会加入森林，然后游戏继续。 当轮到某位玩家进行操作时，森林为空，那么他就输了。 问你当两人都采用最优策略时，谁会赢。 **简要翻译** 给你一个森林，两人轮流操作，每次选一棵树，然后选一个不超过这棵树的秩的正整数 $d$，将深度不超过 $d$ 的点删去，保留其他点在森林中。Alice 为先手，Bob 为后手，无法操作者输。若两人均采用最优策略，谁能赢？ 这棵树的秩是它深度最小的那个叶子的深度。