Poachers
Contest: Technocup 2022 - Elimination Round 3
Difficulty rating: 2500
Tags: dp, games, graphs, trees

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.

Input format:
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$$$.

Output format:
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).

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
NO
YES
NO
YES

Editorial:
Solution below uses Sprague–Grundy theory. Make sure you understand this concept before reading the editorial.
We can note that every position that appears in the game is subtree of one of initial trees or their combinations. This shows that it's sufficient to find grundy-values for all subtrees of initial trees.
Dynamic programming on subtrees will be applied here. We will identify subtree by its root. In each node we will store array of grundy-values for each of possible moves in the game on correspondent subtree. Length of this array is numerically equal to the rank of subtree. We will arrange moves in decreasing by cutting depth order. We will also store grundy-value for subtree itself, it's equal to MEX of grundy-values over all moves.
DP is recalculated in this way:
• If node is a leaf it has one move leading to empty game.
• If node has exactly one child, then we should add grundy-value of child in the end of its array and copy this array in current node. We will recalculate MEX of grundy-values in array explicitely here. We must use the fact that MEX can only increase at this point.
• Suppose that node has multiple children. We will choose one with the smallest rank (shortest array). Let's imagine here, that we cut all arrays by the length of the shortest, as we cannot make moves with cutting depth greater than rank. In the array of current node we will put array, in each position of which lies XOR of grundy-values in correspondent positions over all arrays of children. We should also add in the end of this array XOR of all grundy-values over all children. We should also calculate MEX of grundy-values in constructed array, we will do it explicitly and starting from $$$0$$$, calculated value will be equal to grundy-value of current node.
Why this work fast? We will use coin method of amortyzed analysis. We will remain the invariant that on each array that we track lie at least ($$$3 \cdot$$$ LENGTH $$$-$$$ MEX) coins:
• Each time we calculate MEX explicitly we can use one coin, so this operation is completely paid off.
• In leaf-case we create one array with length $$$1$$$ and put $$$3$$$ coins on it.
• In other cases we will track one of arrays of children as array of current node and stop tracking arrays of other children.
• In there is exactly one child, we extend arrays length by $$$1$$$ and put $$$3$$$ extra coins on it. Remember, we have already showed that MEX recalculation is paid off.
• In case of multiple children: let's fix $$$h$$$ — length of shortest array of chidlren. We will track this array as array of current. There are ($$$\geq 2 \cdot h$$$) coins on this array. As all other arrays are not shorter, they also have ($$$\geq 2 \cdot h$$$) coins each. Let's move $$$h$$$ coins from them to the shortest one, now it has ($$$\geq 3 \cdot h$$$) coins. For each of array (except shortest) we will spend $$$h$$$ coins to recalculate grundy-value in the shortest one, we do XOR= operation here. In the moment we extend array by adding XOR of grundy-values over children we put extra $$$3$$$ coins on it. Note that we lose track of all arrays used here except the shortest one. Note, that there are enough coins to pay off MEX calculation on the shortest array.
The only problem left is that when we are trying to recalculate MEX of some array we have to check if number appears in the array. We can maintain set of all elements of the array, each node should contain set for its array. Number of insert/erase/exist queries to all sets are bounded by $$$4 \cdot n$$$, as we pay off each operation except failed attempt to increase MEX, but this happens ones in each node.
Total complexity: $$$\mathcal{O}(n \cdot \log(n))$$$.