Background

Description

For a two-player, perfect-information, deterministic game, a game tree is a common analysis tool. A game tree is a rooted tree whose nodes are game states. If node B’s parent is A, then state A can transition to state B with a single decision. Each state has a unique player to move, i.e., exactly one side should make the move at that state. We assume the two players alternate moves at all times, meaning adjacent nodes in the tree always have different players to move.

In this problem, we only care about which player wins, and we assume the game cannot end in a draw.

We call the two players Black and White, and the root’s player to move is Black. Clearly, each node has exactly two possible outcomes: Black wins or White wins. If an internal node (i.e., a node that has children) is a Black-to-move node, then this node is winning for Black if and only if at least one of its children is winning for Black; conversely for a White-to-move node. Solving the game tree means determining the outcome at the root.

If we already knew the outcomes of all leaves (nodes without children), the game tree would be easy to solve. However, here the outcomes of all leaves are unknown and need further computation. For a set of leaves $S$, if knowing that every node in $S$ is a win for Black is sufficient to assert that the root is a win for Black, then $S$ is called a Black-winning set. Among Black-winning sets $S$, if for any other Black-winning set $S'$ it holds that $|S| \le |S'|$ (where $|S|$ denotes the number of elements in $S$), then $S$ is a minimal Black-winning set. Similarly, we can define White-winning sets and minimal White-winning sets.

Eden is studying game trees. He noticed that if a leaf belongs to some minimal Black-winning set and also to some minimal White-winning set, then determining this leaf’s outcome is clearly most helpful for determining the root’s outcome. Such leaves are called critical leaf nodes. For a given game tree, Eden wants to know which leaves are critical leaf nodes.

Output Format

Print three space-separated positive integers on a single line: the index of the critical leaf node with the smallest index, the number of critical leaf nodes, and the bitwise XOR of the indices of all critical leaf nodes.

7 
1 
1 
2 
2 
3 
3

4 4 0 

Hint

[Sample explanation]

As shown, black nodes indicate Black-to-move nodes, and white nodes indicate White-to-move nodes.

All minimal Black-winning sets are $\{4, 5\}$ and $\{6, 7\}$.

All minimal White-winning sets are $\{4, 6\}$, $\{4, 7\}$, $\{5, 6\}$, and $\{5, 7\}$.

Therefore, the set of critical leaf nodes is $\{4, 5, 6, 7\}$.

• For $30\%$ of the testdata, $n \le 100$.
• For $40\%$ of the testdata, $n \le 1000$.
• For $50\%$ of the testdata, $n \le 10 ^ 4$, and the tree is randomly generated.
• For $100\%$ of the testdata, $1 \le n \le 2\times 10 ^ 5$, and for node $i$ ($i \ne 1$), the index of its parent is less than $i$.

Translated by ChatGPT 5