#P18386. Art of Data Structures

Art of Data Structures

Art of Data Structures

小青鱼正在 Cup 大学讲授数据结构大师课。这次,他希望你自行设计数据结构:构造一棵有根二叉树 TT,满足每个内部结点恰有两个孩子,并且恰好有 mm 个叶子,分别标记为 1,2,…,m1,2,\ldots,m,每个标记只出现一次。

叶子指没有孩子的结点,内部结点指不是叶子的结点。

二叉树示意图:六个叶子、最大深度5

对于叶子标记组成的集合 SS,定义它在 TT 上的代价为:满足以下两个条件的内部结点 vv 的数量。

  • vv 的子树中至少有一个叶子的标记属于 SS。
  • vv 的子树中至少有一个叶子的标记不属于 SS。

小青鱼给出两棵有根树 T1,T2T_1,T_2。它们都恰有 nn 个结点,结点编号为 11 至 nn,根都是结点 11。他还给出 mm 个有序对 (xi,yi)(x_i,y_i),其中 xix_i 是 T1T_1 的结点,yiy_i 是 T2T_2 的结点;你构造的树中,标记为 ii 的叶子与这个有序对关联。

对于有根树 RR 的结点 uu,记 path⁡(R,u)\operatorname{path}(R,u) 为从 uu 到根的唯一路径上的所有结点组成的集合,包括两个端点。

对于每个 1≤u≤n1\le u\le n,定义两个叶子标记集合:

$$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)\}.$$

根路径示意图:从8到根的路径

你构造的 TT 必须同时满足:

  • 所有结点的深度都不超过 100100,其中根的深度是 11。
  • 上述全部 2n2n 个集合 Q1(u),Q2(u)Q_1(u),Q_2(u) 在 TT 上的代价都不超过 1666616666。

请构造满足要求的二叉树。

输入格式

第一行包含两个整数 n,mn,m(1≤n,m≤1061\le n,m\le 10^6)。

接下来一行包含 n−1n-1 个整数 p2,p3,…,pnp_2,p_3,\ldots,p_n(1≤pi<i1\le p_i<i),其中 pip_i 是 T1T_1 中结点 ii 的父亲。

接下来一行包含 n−1n-1 个整数 p2′,p3′,…,pn′p'_2,p'_3,\ldots,p'_n(1≤pi′<i1\le p'_i<i),其中 pi′p'_i 是 T2T_2 中结点 ii 的父亲。

接下来 mm 行,每行包含两个整数 xi,yix_i,y_i(1≤xi,yi≤n1\le x_i,y_i\le n),表示第 ii 个有序对。当 n=1n=1 时,两棵树都没有需要输入的父亲编号。

输出格式

输出一行整数,按照以下递归规则描述你构造的二叉树:

  • 一个标记为 ii 的叶子用整数 ii 表示。
  • 一个内部结点用整数 00,紧接着它的左子树描述和右子树描述表示。

因此,每个 11 至 mm 的整数必须恰好出现一次,每个 00 表示一个内部结点。输出必须完整描述一棵满足要求的树;若存在多个合法构造,可以输出任意一个。

例如,0 1 0 2 3 表示根的左孩子是标记为 11 的叶子,根的右孩子是内部结点,后者的两个孩子分别是标记为 22 和 33 的叶子。

样例输入 1

1 1
1 1

样例输出 1

1

样例解释 1

二叉树只有标记为 11 的一个叶子,它的深度为 11,所有待检查集合的代价都是 00。

样例输入 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