CF1585G.Poachers

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.

爱丽丝和鲍勃是两名在森林中砍伐树木的盗猎者。

森林是一组零棵或多棵树的集合。树是一种无环的连通图。有根树具有一个被称为“根”的特殊顶点。顶点 $v$ 的父节点是指从 $v$ 到根的最短路径上紧邻 $v$ 的下一个顶点。顶点 $v$ 的子节点是指所有以 $v$ 为父节点的顶点。若一个顶点没有子节点，则称其为叶节点。

在本题中，我们定义一个顶点的深度为从该顶点到根的简单路径上所包含的顶点个数。一棵树的秩定义为该树所有叶节点深度中的最小值。

初始时，给定一个由若干有根树构成的森林。爱丽丝与鲍勃在该森林上进行一场博弈，两人轮流行动，爱丽丝先行。在每轮行动开始时，当前玩家需从森林中选择一棵树；接着选择一个正整数切割深度，该值不得超过所选树的秩；然后移除该树中所有深度小于等于该切割深度的所有顶点。剩余顶点构成若干棵新的有根树：每棵新树的根为原树中在切割前深度最小的剩余顶点。这些新树全部加入游戏森林中，游戏继续进行。

若某位玩家在自己回合开始时森林为空，则该玩家判负。

请判断：当双方均采取最优策略时，爱丽丝是否必胜。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 5 \cdot 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）—— 初始森林中顶点的总数。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$0 \leq p_i \leq n$）—— 森林的描述。若 $p_i = 0$，则第 $i$ 个顶点是一棵树的根；否则 $p_i$ 是顶点 $i$ 的父节点。保证 $p$ 描述了一个合法的有根树森林。

保证所有测试用例的 $n$ 之和不超过 $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).

对于每个测试用例，如果 Alice 获胜，则输出 "YES"（不带引号），否则输出 "NO"（不带引号）。每个字母可以以任意大小写形式输出（大写或小写）。

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.

在第一个测试用例中，Bob 采用对称策略，因此 Alice 无法获胜。

在第二个测试用例中，Alice 可选择第二棵树并以切割深度 $1$ 进行操作，从而得到一片她自身拥有对称策略的森林。

在第三个测试用例中，唯一一棵树的秩为 $2$，而 Alice 的所有可能操作均导致失败。Bob 要么可使森林变为对他自身具有对称策略的状态，要么直接清空整片森林。

在第四个测试用例中，所有叶子节点的深度均相同，因此 Alice 可通过一次操作清空整片森林。