Tree Factory

题意翻译

Bytelandian Tree Factory生产各种工业用途的树，你的任务是为一个特别大的重要订单优化生产 问题中的树是一棵有$n$个节点的有根树，每个顶点用不同的整数标记为$[0,1,...,n-1]$，其中$0$标记着根节点，且对于任何非根节点$v$，它的父节点的标号$p(v)$要比它的标号$v$要小。 工厂里所有的树都是用竹子做的（可能不准确但不影响题意理解），这种竹子是有根的树，且每个节点只有一个子节点（除了叶子节点没有子节点），也就是说，它是直线形的。加工前，竹子的顶点可以随意标注。 要加工竹子为一棵树，可以进行这样的操作：选择任意一个不是根节点且父节点也不是根节点的节点$v$，将它的父节点变成原先父节点的父节点即$p(p(v))$，而其它节点的父节点都保持不变，$v$的子树也不会改变。 效率是至关重要的，所以在加工出所需要的树的前提下你应当最小化操作数。现在请你构造任何最优的操作序列以生成所需要的树 注意：加工出的结果树的标签必须和所需要的树的标签一致，即根节点标签相同，其它所有具有相同标签的子节点$v$，其父节点标签$p(v)$也应相同。 数据保证任何输入都至少有一种可行的方案，且最优操作序列最多包含$10^6$个操作。而不符合这些条件的$hack$数据都是无效的（$codeforces$允许$hack$其它人，洛谷上现在可以无视这句）。 ### 输入格式 输入第一行是一个正整数$n$，表示需求树中节点的数量$(2≤n≤10^5)$ 第二行有$n-1$个整数$[p_1,p_2,...,p_{n-1}]$，$p_i$表示需求树上节点标签为$i$的父节点标签$p(i)(1≤p_i≤i)$ ### 输出格式 输出第一行为$n$个不同的整数$[id_1,id_2,...,id_n]$，$id_i$表示使用的第$i$根竹子上的节点数量（即从根节点开始第几个子节点为空)$(0≤id_i<n)$ 第二行输出一个正整数$k$，表示你输出操作序列中的操作数$(0≤k≤10^6)$ 第三行输出$k$个整数$[v_1,v_2,...,v_k]$，表示操作序列，第$i$个整数表示操作“将$v_i$的父节点从$p(v_i)$变成$p(p(v_i))$”。每个操作都应当是合法的操作（即$v_i$和$p(v_i)$此时都不是根节点）。

题目描述

Bytelandian Tree Factory produces trees for all kinds of industrial applications. You have been tasked with optimizing the production of a certain type of tree for an especially large and important order. The tree in question is a rooted tree with $ n $ vertices labelled with distinct integers from $ 0 $ to $ n - 1 $ . The vertex labelled $ 0 $ is the root of the tree, and for any non-root vertex $ v $ the label of its parent $ p(v) $ is less than the label of $ v $ . All trees at the factory are made from bamboo blanks. A bamboo is a rooted tree such that each vertex has exactly one child, except for a single leaf vertex with no children. The vertices of a bamboo blank can be labelled arbitrarily before its processing is started. To process a bamboo into another tree a single type of operation can be made: choose an arbitrary non-root vertex $ v $ such that its parent $ p(v) $ is not a root either. The operation consists of changing the parent of $ v $ to its parent's parent $ p(p(v)) $ . Note that parents of all other vertices remain unchanged, in particular, the subtree of $ v $ does not change. Efficiency is crucial, hence you have to minimize the number of operations to make the desired tree from a bamboo blank. Construct any optimal sequence of operations to produce the desired tree. Note that the labelling of the resulting tree has to coincide with the labelling of the desired tree. Formally, the labels of the roots have to be equal, and for non-root vertices with the same label the labels of their parents should be the same. It is guaranteed that for any test present in this problem an answer exists, and further, an optimal sequence contains at most $ 10^6 $ operations. Note that any hack that does not meet these conditions will be invalid.

输入输出格式

输入格式

The first line contains a single integer $ n $ — the number of vertices in the tree ( $ 2 \leq n \leq 10^5 $ ). The second line contains $ n - 1 $ integers $ p(1), \ldots, p(n - 1) $ — indices of parent vertices of $ 1, \ldots, n - 1 $ respectively ( $ 0 \leq p(i) < i $ ).

输出格式

In the first line, print $ n $ distinct integers $ id_1, \ldots, id_n $ — the initial labelling of the bamboo blank starting from the root vertex ( $ 0 \leq id_i < n $ ). In the second line, print a single integer $ k $ — the number of operations in your sequence ( $ 0 \leq k \leq 10^6 $ ). In the third line print $ k $ integers $ v_1, \ldots, v_k $ describing operations in order. The $ i $ -th operation consists of changing $ p(v_i) $ to $ p(p(v_i)) $ . Each operation should be valid, i.e. neither $ v_i $ nor $ p(v_i) $ can be the root of the tree at the moment.

输入输出样例

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