#P18386. Art of Data Structures
Art of Data Structures
Art of Data Structures
小青鱼正在 Cup 大学讲授数据结构大师课。这次,他希望你自行设计数据结构:构造一棵有根二叉树 ,满足每个内部结点恰有两个孩子,并且恰好有 个叶子,分别标记为 ,每个标记只出现一次。
叶子指没有孩子的结点,内部结点指不是叶子的结点。

对于叶子标记组成的集合 ,定义它在 上的代价为:满足以下两个条件的内部结点 的数量。
- 的子树中至少有一个叶子的标记属于 。
- 的子树中至少有一个叶子的标记不属于 。
小青鱼给出两棵有根树 。它们都恰有 个结点,结点编号为 至 ,根都是结点 。他还给出 个有序对 ,其中 是 的结点, 是 的结点;你构造的树中,标记为 的叶子与这个有序对关联。
对于有根树 的结点 ,记 为从 到根的唯一路径上的所有结点组成的集合,包括两个端点。
对于每个 ,定义两个叶子标记集合:
$$Q_1(u)=\{i\mid x_i\in\operatorname{path}(T_1,u)\},\qquad Q_2(u)=\{i\mid y_i\in\operatorname{path}(T_2,u)\}.$$
你构造的 必须同时满足:
- 所有结点的深度都不超过 ,其中根的深度是 。
- 上述全部 个集合 在 上的代价都不超过 。
请构造满足要求的二叉树。
输入格式
第一行包含两个整数 ()。
接下来一行包含 个整数 (),其中 是 中结点 的父亲。
接下来一行包含 个整数 (),其中 是 中结点 的父亲。
接下来 行,每行包含两个整数 (),表示第 个有序对。当 时,两棵树都没有需要输入的父亲编号。
输出格式
输出一行整数,按照以下递归规则描述你构造的二叉树:
- 一个标记为 的叶子用整数 表示。
- 一个内部结点用整数 ,紧接着它的左子树描述和右子树描述表示。
因此,每个 至 的整数必须恰好出现一次,每个 表示一个内部结点。输出必须完整描述一棵满足要求的树;若存在多个合法构造,可以输出任意一个。
例如,0 1 0 2 3 表示根的左孩子是标记为 的叶子,根的右孩子是内部结点,后者的两个孩子分别是标记为 和 的叶子。
样例输入 1
1 1
1 1
样例输出 1
1
样例解释 1
二叉树只有标记为 的一个叶子,它的深度为 ,所有待检查集合的代价都是 。
样例输入 2
3 3
1 1
1 2
1 1
2 2
3 3
样例输出 2
0 1 0 2 3
样例输入 3
5 8
1 2 3 4
1 1 1 1
1 1
2 1
3 2
4 2
5 3
5 5
1 5
3 4
样例输出 3
0 0 1 0 0 3 8 0 2 7 0 4 0 5 6