6456: 树的 DFS I
[Creator : ]
Description
给定一棵 $n$ 个节点的树。
节点的编号为 $1 \sim n$,其中 $1$ 号节点为根节点,每个节点的编号都大于其父节点的编号。
请输出该树的 DFS 序,我们规定,当遍历(或回溯)到某一节点时,下一个遍历的目标应该是它的未经遍历的子节点中编号最小的那一个子节点。
例如,上图实例中,遍历根节点为 $1$ 号节点的子树,则子树内各节点的遍历顺序为 $[1,2,3,5,6,8,7,9,4]$。
节点的编号为 $1 \sim n$,其中 $1$ 号节点为根节点,每个节点的编号都大于其父节点的编号。
请输出该树的 DFS 序,我们规定,当遍历(或回溯)到某一节点时,下一个遍历的目标应该是它的未经遍历的子节点中编号最小的那一个子节点。
例如,上图实例中,遍历根节点为 $1$ 号节点的子树,则子树内各节点的遍历顺序为 $[1,2,3,5,6,8,7,9,4]$。
Input
第一行包含两个整数 $n\ (2≤n≤2×10^5)$。
第二行包含 $n−1$ 个整数 $p_2,p_3,…,p_n$,其中 $p_i$ 表示第 $i$ 号节点的父节点的编号。
第二行包含 $n−1$ 个整数 $p_2,p_3,…,p_n$,其中 $p_i$ 表示第 $i$ 号节点的父节点的编号。
Output
一行包括 $n$ 个数字,表示该树的 DFS 序。
Sample 1 Input
9
1 1 1 3 5 3 5 7
Sample 1 Output
1 2 3 5 6 8 7 9 4