← 返回题目
题库练习 「NOI2020」超现实树
← 上一题 下一题 →

A5927 | 「NOI2020」超现实树

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

下课铃声响起，机房里的两位女生从座位上站起来。（下面用 $\mathbf{X1},\mathbf{X2}$ 代指两人）

$\mathbf{X2}$：省选前的集训真难熬啊……听课、考试、讲评、补题——对于现在的我来说，即使在梦里想到一道数据结构题，也会不由自主地开始思考吧。

$\mathbf{X1}$：重复训练对我来说似乎并不是什么负担，但我确实感觉到解决题目带来的愉悦感在最近逐渐减弱了。也许我们需要一些精神上的“刺激”：一些不拘泥于繁复技术的智力游戏，来让我们找回对于数学和算法的兴趣。

$\mathbf{X2}$：咦，我好像收到了一封用英文写的短信，似乎是……数学书上的一些片段。

$\mathbf{X1}$：我来翻译一下短信的内容。

> **定义**：本文所述的树是归纳定义的：单独的结点构成一棵树，以一棵树作为左（或右）孩子可以构成一棵树，以两棵树分别作为左、右孩子也可以构成一棵树。仅由以上规则用有限步生成的所有结构被称为树。

$\mathbf{X2}$：也就是说，这里所说的树是指**非空**、**有根**、**区分左右孩子的二叉树**。

$\mathbf{X1}$：的确如此。接下来书上定义了两棵树的同构。

> **定义**：称两棵树 $T, T'$ 同构，记做 $T\equiv T'$，由以下四条规则定义：
>
> 1. 由单独结点构成的树是彼此同构的；
> 2. 如果两棵树的根结点均只有左子树，并且它们的左子树同构，那么这两棵树是同构的；
> 3. 如果两棵树的根结点均只有右子树，并且它们的右子树同构，那么这两棵树是同构的；
> 4. 如果两棵树的根结点均有左、右子树，并且它们的左、右子树分别对应同构，那么这两棵树是同构的。

很明显，同构关系构成了所有树上的一个等价关系。为了方便，我们将同构的树看作相同的树。

$\mathbf{X2}$：将同构的树看成相同的树就是说树的结点是彼此相同的。简单地说，两棵树同构当且仅当**他们在结点无标号**、**区分左右孩子的意义下相同**；我们说两棵树不同，当且仅当它们不同构。

$\mathbf{X1}$：书里还定义了树的**叶子**：和通常的定义一样，叶子指**没有任何孩子的结点**。

$\mathbf{X2}$：这和我们熟悉的定义完全一致。嘛，数学家真是有点啰嗦……恐怕只有 $\mathbf{X3}$ 那种家伙会喜欢这种做派吧。

$\mathbf{X1}$：我倒是对此不太反感——比起基于经验的“直觉”，准确的定义和严谨的证明还是更加让人安心。你看，下一个定义就没有那么直观了。

> **定义**：称一棵树 $T$ **单步替换**成为 $T'$，如果将 $T$ 的某一**叶子结点**替换为另一棵树 $T''$ 得到的树与 $T'$ 同构，记做 $T \rightarrow T'$；称一棵树 $T$ **替换**成为 $T'$，记做 $T\rightarrow^{\star} T'$，如果存在自然数 $n\ge1$ 和树 $T_1, T_2, \dots, T_n$，使得 $T\equiv T_1\to T_2\to \dots \to T_n\equiv T'$。

$\mathbf{X2}$：我来想想……所谓替换，就是删掉某个叶子结点并在对应的位置放入另一棵树，就像那个叶子结点“长出了”一个更大的子树一样；一棵树替换成为另一棵树，说明它可以经由**零次**、**一次或多次**单步替换得到那棵树。哦……我明白了！举例来说，任何一棵树都可以替换成它本身，换言之对于树 $T$，都有 $T\rightarrow^{\star} T$。下面这个图片可以帮助理解单步替换和替换的含义。

![image-20200819222531493.png](/uploads/acgo/image/59a13db430f9bf88_e67aeaf448de.png)

**定义**：对于一棵树 $T$，定义 $\operatorname{grow}(T)$ 表示 $T$ 所能替换构成的树的集合，即 $\operatorname{grow}(T) = \{T' \mid T \rightarrow^\star T'\}$。更近一步，如果 $\mathscr T = \{T_1, T_2, \dots, T_n\}$ 是一个树的有限集合，定义 $\operatorname{grow}(\mathscr T)$ 为所有 $\operatorname{grow}(T_i)$ 的并集，其中 $i = 1, 2, \dots, n$。即
$$ \operatorname{grow}(\mathscr T) = \bigcup_{T_i \in \mathscr T} \operatorname{grow}(T_i) $$
$\mathbf{X2}$：我们把 $\operatorname{grow}(T)$ 称作树的集合 $T$ **所生长得到的集合**吧——也就是说，树的集合 $T$ 所生长得到的集合包含所有可以被某个 $T \in \mathscr T$ 替换得到的树。不妨把树的集合叫做**树林**。不太严谨地说，一个树林所生长得到的新树林就是其中所有树、以所有可能的方式生长得到的树林。显而易见，一个非空树林所生长得到的树林都是无穷树林。

但这个无穷树林，或者说 $\operatorname{grow}(\mathscr T)$ ，并不一定包含所有的树——更进一步，它甚至不一定包含“几乎所有”的树。

$\mathbf{X1}$：让我来补充一下：我们称一个树林是**几乎完备**的（或称**几乎包含了所有的树**），如果仅有有限多的树不在其中。对于一个有限树林 $\mathscr T$ ，$\operatorname{grow}(\mathscr T)$ 要么包含了所有的树，要么包含了几乎所有的树，要么存在无穷多棵树不在其中。如果这是一道OI 题，出题人一定会**在样例中给出三种情况的例子**吧。书上的关键定理也用了和我们相同的定义。

> **定理**（**几乎完备的可判定性**）：一个树的集合是**几乎完备**的，如果仅有有限棵树不在其中。那么，对于一个给定的树的有限集合 $\mathscr T$，存在高效的算法判定 $\operatorname{grow}(\mathscr T )$ 是否是几乎完备的。

$\mathbf{X2}$：这个问题变成一个纯粹的 OI 题目了！让我用我们的语言来重述一下题意：**给定一个有限大小的树林** $T$ ，**判定** $\operatorname{grow}(\mathscr T )$ **是否是几乎完备的**，**即是否仅有有限棵树不能被树林中所包含的树生长得到**。

$\mathbf{X1}$：也就是说，给定一个有限的树的集合 $\mathscr T$ ，判定是否仅有有限个树 $T$，满足 $T \notin \operatorname{grow}(\mathscr T)$。所谓 $T \notin \operatorname{grow}(\mathscr T)$，就是说不存在 $T' \in \mathscr T$，使得 $T'\rightarrow ^\star T$。这和通常的 OI 题目的确非常不同：我甚至没有想到这个问题的一个算法。

$\mathbf{X2}$：我也一样，不过我很久没有感受到这种解决未知问题的冲动了。

输入格式

从文件 surreal.in 中读入数据。

本题有多组测试数据，输入文件的第一行包含一个正整数 $T$，表示测试数据的组数。接下来包含恰好 $T$ 组测试数据，每组测试数据具有以下的格式：

第一行是一个正整数 $m$，表示树的集合中树的个数。接下来按照以下格式输入 $m$ 棵树：

- 首先是一个正整数 $n$，表示树中的结点个数，结点编号为 $1, 2, \dots, n$；

- 接下来 $n$ 行每行两个非负整数，其中第 $i$ 行从左到右包含用空格隔开的 $l_i$ 和 $r_i$，分别表示 $i$ 号结点左、右孩子结点的编号。如果左（或右）孩子不存在，那么 $l_i$
（或 $r_i$）为 $0$。当然，叶结点一定满足 $l_i = r_i = 0$。

- 输入数据保证构成一棵以 $1$ 号结点作为根结点的树。**请注意**：结点的编号只是为了方便输入，任何同构的树都被视为是相同的。

所输入的 $m$ 棵树中可能存在彼此同构的树；如果去除这些重复的树（即每种同构的树只留下一个），它们可以构成一个树的集合 $\mathscr T$。你需要判定这一树的集合所生长得到的集合 $\operatorname{grow}(\mathscr T )$ 是否是几乎完备的。

输出格式

输出到文件 surreal.out 中。

输出包含 $T$ 行，分别表示 $T$ 组测试数据的答案。其中，第 $i$ 行输出一个字符串：如果第 $i$ 组测试数据所输入的树的集合所生长得到的集合是几乎完备的（换言之，仅有有限棵树不能被其生长得到），那么输出 Almost Complete；否则输出 No。**请注意输出字符串的拼写和大小写**。

输入输出样例

输入 #1
1
1
1
0 0
输出 #1
Almost Complete
输入 #2
1
3
3
2 3
0 0
0 0
2
2 0
0 0
2
0 2
0 0
输出 #2
Almost Complete
输入 #3
1
2
3
2 3
0 0
0 0
2
2 0
0 0
输出 #3
No
C++ 编辑器
输入
输出