P6776 [NOI2020] Surreal Tree

The class-ending bell rings, and two girls in the computer lab stand up from their seats. (In the following, $\mathbf{X1}$ and $\mathbf{X2}$ refer to the two of them.) $\mathbf{X2}$: The training camp before the NOI Qualifier is really hard to endure... Lectures, exams, reviews, solving extra problems—at this point, even if I dream about a data structure problem, I probably start thinking about it unconsciously. $\mathbf{X1}$: Repetitive training does not seem like a burden to me, but I do feel that the pleasure of solving problems has been gradually weakening lately. Maybe we need some mental “stimulation”: some brain games that are not tied down by complicated techniques, to help us regain our interest in math and algorithms. $\mathbf{X2}$: Huh, I think I received an English text message. It seems to be... some fragments from a math book.

$\mathbf{X1}$: Let me translate the message. > Definition: The trees described in this text are defined inductively: a single node forms a tree; taking a tree as the left (or right) child forms a tree; taking two trees as the left and right children respectively also forms a tree. All structures generated by the above rules in finitely many steps are called trees. $\mathbf{X2}$: So the “trees” here are **non-empty, rooted binary trees with distinguished left and right children**. $\mathbf{X1}$: Exactly. Next, the book defines isomorphism of two trees. > Definition: Two trees $T$ and $T^{\prime}$ are called isomorphic, written $T \equiv T^{\prime}$, defined by the following four rules: > 1. Trees consisting of a single node are isomorphic to each other. > 2. If the roots of two trees both have only a left subtree, and their left subtrees are isomorphic, then these two trees are isomorphic. > 3. If the roots of two trees both have only a right subtree, and their right subtrees are isomorphic, then these two trees are isomorphic. > 4. If the roots of two trees both have left and right subtrees, and their left subtrees are isomorphic correspondingly and their right subtrees are isomorphic correspondingly, then these two trees are isomorphic. > > Obviously, the isomorphism relation forms an equivalence relation on the set of all trees. For convenience, we regard isomorphic trees as the same tree. $\mathbf{X2}$: Treating isomorphic trees as the same means the nodes are considered identical. Simply put, two trees are isomorphic if and only if **they are the same when nodes are unlabeled and left/right children are distinguished**. We say two trees are different if and only if they are not isomorphic. $\mathbf{X1}$: The book also defines **leaves** of a tree: same as usual, a leaf is a **node with no children**. $\mathbf{X2}$: That matches the definition we know. Well, mathematicians are really a bit wordy... Probably only someone like $\mathbf{X3}$ would enjoy this style. $\mathbf{X1}$: I do not really mind it—compared with experience-based “intuition”, precise definitions and rigorous proofs feel more reassuring. Look, the next definition is not so intuitive. > Definition: We say a tree $T$ **single-step replaces** into $T^{\prime}$ if replacing some **leaf node** of $T$ with another tree $T^{\prime \prime}$ yields a tree isomorphic to $T^{\prime}$, written $T \rightarrow T^{\prime}$. We say a tree $T$ **replaces** into $T^{\prime}$, written $T \rightarrow^{\star} T^{\prime}$, if there exist a natural number $n \geq 1$ and trees $T_{1}, T_{2}, \ldots, T_{n}$ such that $T \equiv T_{1} \rightarrow T_{2} \rightarrow \cdots \rightarrow T_{n} \equiv T^{\prime}$. $\mathbf{X2}$: Let me think... “Replacement” means deleting a leaf node and putting another tree at that position, like the leaf node “grows” a larger subtree. If a tree can replace into another tree, it means the latter can be obtained through **zero, one, or multiple** single-step replacements. Oh... I see! For example, any tree can replace into itself; in other words, for a tree $T$, we always have $T \rightarrow^{\star} T^{\prime}$. The picture below can help understand the meanings of single-step replacement and replacement.  $\mathbf{X1}$: You are right. In particular, any tree can replace into infinitely many different trees, and only the single-node tree can replace into any other tree. The book also defines something like this. > Definition: For a tree $T$, define $\operatorname{grow}(T)$ as the set of trees that $T$ can obtain by replacement, i.e. $\operatorname{grow}(T)=\left\{T^{\prime} \mid T \rightarrow^{\star} T^{\prime}\right\}$. Furthermore, if $\mathscr{T}=\left\{T_{1}, T_{2}, \ldots, T_{n}\right\}$ is a finite set of trees, define $\operatorname{grow}(\mathscr{T})$ as the union of all $\operatorname{grow}\left(T_{i}\right)$ for $i=1,2,\ldots,n$, that is, > $$\operatorname{grow}(\mathscr{T})=\bigcup_{T_{i} \in \mathscr{T}} \operatorname{grow}\left(T_{i}\right)$$ $\mathbf{X2}$: Let us call $\operatorname{grow}(\mathscr{T})$ the **set grown from** the tree set $\mathscr{T}$. That is, it contains all trees that can be obtained by replacing from some $T \in \mathscr{T}$. We may call a set of trees a **forest**. Informally, the new forest grown from a forest is the forest of all trees grown from all trees in it, in all possible ways. Obviously, the forest grown from any non-empty forest is infinite. But this infinite forest, i.e. $\operatorname{grow}(\mathscr{T})$, does not necessarily contain all trees—more strongly, it does not even necessarily contain “almost all” trees. $\mathbf{X1}$: Let me add: we call a forest **almost complete** (or **almost contains all trees**) if only finitely many trees are not in it. For a finite forest $\mathscr{T}$, $\operatorname{grow}(\mathscr{T})$ either contains all trees, or contains almost all trees, or there are infinitely many trees not in it. If this were an OI problem, the problem setter would surely **give examples of all three cases in the samples**. The key theorem in the book also uses the same definition as ours. > **Theorem** (**Decidability of Almost Completeness**): A set of trees is **almost complete** if only finitely many trees are not in it. Then, for a given finite set of trees $\mathscr{T}$, there exists an efficient algorithm to determine whether $\operatorname{grow}(\mathscr{T})$ is almost complete. $\mathbf{X2}$: This becomes a pure OI problem! Let me restate it in our words: **given a finite forest $\mathscr{T}$, determine whether $\operatorname{grow}(\mathscr{T})$ is almost complete, i.e. whether only finitely many trees cannot be grown from the trees in the forest**. $\mathbf{X1}$: That is, given a finite set of trees $\mathscr{T}$, determine whether there are only finitely many trees $T$ such that $T \notin \operatorname{grow}(\mathscr{T})$. Saying $T \notin \operatorname{grow}(\mathscr{T})$ means there is no $T^{\prime} \in \mathscr{T}$ such that $T^{\prime} \rightarrow^{\star} T$. This is indeed very different from usual OI problems: I cannot even think of an algorithm for it. $\mathbf{X2}$: Same here, but I have not felt this urge to solve an unknown problem for a long time.

This problem contains multiple sets of testdata. The first line of the input file contains a positive integer $N$, indicating the number of test cases. Then there are exactly $N$ test cases. Each test case has the following format: The first line contains a positive integer $m$, indicating the number of trees in the set. Then $m$ trees are given in the following format: - First, a positive integer $n$, indicating the number of nodes in the tree. The nodes are numbered $1,2,\ldots,n$. - Then $n$ lines follow, each containing two non-negative integers. In the $i$-th line, from left to right, there are $l_i$ and $r_i$ separated by a space, representing the indices of the left and right child of node $i$. If the left (or right) child does not exist, then $l_i$ (or $r_i$) is $0$. Of course, a leaf must satisfy $l_i=r_i=0$. - The input is guaranteed to form a tree rooted at node $1$. **Note**: node indices are only for input convenience; any isomorphic trees are considered the same. Among the $m$ input trees, some may be isomorphic. After removing duplicates (i.e. keeping only one tree for each isomorphism class), they form a set of trees $\mathscr{T}$. You need to determine whether the set grown from this tree set, $\operatorname{grow}(\mathscr{T})$, is almost complete.

Output $N$ lines, giving the answers for the $N$ test cases. In the $i$-th line, output a string: if the set grown from the input tree set of the $i$-th test case is almost complete (in other words, only finitely many trees cannot be grown from it), output `Almost Complete`; otherwise output `No`. **Note the spelling and letter case of the output strings**.

#### Explanation for Sample 2 This sample contains only one test case, where the tree set $\mathscr{T}$ contains three trees, as shown in the figure below. It is easy to see that only the single-node tree is not in $\operatorname{grow}(\mathscr{T})$. Therefore it contains almost all trees, hence it is almost complete.  #### Explanation for Sample 3 This sample contains only one test case, where the tree set $\mathscr{T}$ contains two trees. It is easy to see that for all $n \geq 2$, the chain-shaped tree with $n$ nodes where every non-leaf node has only a right child is not in $\operatorname{grow}(\mathscr{T})$. Hence there are infinitely many trees not in $\operatorname{grow}(\mathscr{T})$, and $\mathscr{T}$ is not almost complete. #### Sample 4 See surreal/surreal4.in and surreal/surreal4.ans in the contestant directory. --- ### Constraints **All data satisfy**: $\sum n \leq 2 \times 10^{6}$, $\sum m \leq 2 \times 10^{6}$, $\max h \leq 2 \times 10^{6}$, $N \leq 10^{2}$. Here, $\sum n$ is the sum of the numbers of nodes of all trees appearing in all test cases of this subtask; $\sum m$ is the total number of trees appearing in all test cases of this subtask; $\max h$ is the maximum height among all trees appearing in this subtask (a single-node tree has height $1$). The entries $\sum n$, $\sum m$, and $\max h$ in the table below have the same meanings as above, and describe the constraints for each subtask. **Special properties**: Below are explanations of the four special properties mentioned in the table. - Special property $1$: For each test case in this subtask, $m \leq 4$, i.e. the set contains at most $4$ trees. - Special property $2$: For each test case in this subtask, all trees in the set have the same height. - Special property $3$: For each test case in this subtask, the set contains only chains (in other words, every non-leaf node has exactly one child). - Special property $4$: For each test case in this subtask, the set contains only trees satisfying one of the following two conditions: - Every non-leaf node has exactly one child. - There are exactly two leaf nodes with the same parent, and except for these three nodes, every other node has exactly one child. The specific limits for each subtask are given in the table below: | Subtask ID | $N$ | $\sum n$ | $\sum m$ | $\max h$ | Special Properties | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $100$ | $\le 10^3$ | $\le 10^3$ | $\le 1$ | None | | $2\sim 3$ | $100$ | $\le 10^3$ | $\le 10^3$ | $\le 2$ | Property $1$ | | $4$ | $100$ | $\le 10^6$ | $\le 10^6$ | $\le 4$ | None | | $5$ | $100$ | $\le 10^6$ | $\le 10^6$ | $\le 5$ | Property $2$ | | $6$ | $100$ | $\le 10^6$ | $\le 10^6$ | $\le 8$ | None | | $7$ | $100$ | $\le 10^6$ | $\le 10^6$ | $\le 9$ | Property $2$ | | $8$ | $100$ | $\le 10^6$ | $\le 10^6$ | $\le 10$ | None | | $9$ | $100$ | $\le 10^6$ | $\le 10^6$ | $\le 10^6$ | Property $3$ | | $10$ | $20$ | $\le 10^3$ | $\le 100$ | $\le 10^3$ | Property $4$ | | $11$ | $20$ | $\le 2\times 10^3$ | $\le 2\times 10^3$ | $\le 2\times 10^3$ | Property $4$ | | $12$ | $20$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | Property $4$ | | $13$ | $20$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | Property $4$ | | $14$ | $20$ | $\le 800$ | $\le 200$ | $\le 800$ | None | | $15$ | $20$ | $\le 10^3$ | $\le 100$ | $\le 10^3$ | None | | $16$ | $20$ | $\le 2\times 10^3$ | $\le 2\times 10^3$ | $\le 2\times 10^3$ | None | | $17$ | $40$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | None | | $18$ | $40$ | $\le 6\times 10^5$ | $\le 6\times 10^5$ | $\le 6\times 10^5$ | None | | $19$ | $40$ | $\le 9\times 10^5$ | $\le 9\times 10^5$ | $\le 9\times 10^5$ | None | | $20$ | $40$ | $\le 1.2\times 10^6$ | $\le 1.2\times 10^6$ | $\le 1.2\times 10^6$ | None | | $21$ | $40$ | $\le 1.5\times 10^6$ | $\le 1.5\times 10^6$ | $\le 1.5\times 10^6$ | None | | $22\sim 25$ | $40$ | $\le 2\times 10^6$ | $\le 2\times 10^6$ | $\le 2\times 10^6$ | None | Translated by ChatGPT 5