← 返回题目列表

Codeforces · 1225/F

F. 树工厂

中文机器翻译题面 查看原题

Bytelandian Tree Factory 生产用于各种工业应用的树木。您的任务是优化特定类型树木的生产,以满足特别大且重要的订单。

所讨论的树是一棵有根树,其 $$$n$$$ 顶点标记有从 $$$0$$$ 到 $$$n - 1$$$ 的不同整数。标记为 $$$0$$$ 的顶点是树的根,对于任何非根顶点 $$$v$$$,其父顶点 $$$p(v)$$$ 的标签小于 $$$v$$$ 的标签。

工厂里的所有树木都是由竹坯制成的。竹子是一棵有根树,除了没有子节点的单个叶顶点外,每个顶点都只有一个子节点。在开始加工之前,可以对竹毛坯的顶点进行任意标记。

要将竹子处理成另一棵树,可以进行单一类型的操作:选择任意非根顶点 $$$v$$$ ,使其父节点 $$$p(v)$$$ 也不是根。该操作包括将 $$$v$$$ 的父级更改为其父级的父级 $$$p(p(v))$$$。请注意,所有其他顶点的父节点保持不变,特别是 $$$v$$$ 的子树不会改变。

效率至关重要,因此您必须最大限度地减少操作次数,才能从竹毛坯中制作出所需的树。构造任何最佳操作序列以生成所需的树。

请注意,生成的树的标签必须与所需树的标签一致。形式上,根的标签必须相等,并且对于具有相同标签的非根顶点,其父节点的标签应该相同。

保证对于此问题中存在的任何测试都存在答案,并且进一步,最佳序列最多包含 $$$10^6$$$ 操作。请注意,任何不满足这些条件的 hack 都将无效。

输入

第一行包含一个整数 $$$n$$$ — 树中的顶点数 ($$$2 \leq n \leq 10^5$$$)。

第二行包含 $$$n - 1$$$ 整数 $$$p(1), \ldots, p(n - 1)$$$ - 分别为 $$$1, \ldots, n - 1$$$ 的父顶点索引 ($$$0 \leq p(i) < i$$$)。

输出

在第一行中,打印 $$$n$$$ 不同的整数 $$$id_1, \ldots, id_n$$$ - 从根顶点开始的竹毛坯的初始标签 ($$$0 \leq id_i < n$$$)。

在第二行中,打印单个整数 $$$k$$$ — 序列中的操作数 ($$$0 \leq k \leq 10^6$$$)。

在第三行打印 $$$k$$$ 整数 $$$v_1, \ldots, v_k$$$ 按顺序描述操作。第 $$$i$$$ 操作包括将 $$$p(v_i)$$$ 更改为 $$$p(p(v_i))$$$。每个操作都应该是有效的,即 $$$v_i$$$ 和 $$$p(v_i)$$$ 都不能是此时树的根。

示例

输入 #1

5
0 0 1 1

输出 #1

0 2 1 4 3
2
1 3

输入 #2

4
0 1 2

输出 #2

0 1 2 3
0