UOJ Logo Universal Online Judge

UOJ

#669. 【UNR #5】排名预测

附件下载 统计

UOI 的规矩是一些成熟稳重的外星大象制定的,所以大D米 AK 了也不准离场。

无聊的大D米决定预测一下排名。他对 $n$ 名参赛选手的水平进行了建模,形成了一棵大小为 $n$ 的有根树 $T$,根为 $1$,表示大D米自己。设节点 $x$ 的父亲为 $\mathrm{fa}[x]$,保证 $\mathrm{fa}[x] < x$。

根据大D米的建模,$\mathrm{fa}[x]$ 的水平是严格比 $x$ 高的,排名应该在他前面。其他人的排名没那么好确定,但是这棵树上同一个子树的人思维方式很接近,排名连续比较合理。

形式化地,对树 $T$,我们这样定义一个 ddm 过程,用于确定选手的可能排名:

  • 令当前已经考虑的节点集合为 $M$,当前正在考虑的节点为 $x$。初始时 $M=\{x\}$ 且 $x=1$。
  • 重复如下过程直到所有节点都在 $M$ 中:
    • 若 $x$ 的所有儿子均在 $M$ 中,则将 $x$ 改为 $\mathrm{fa}[x]$;
    • 否则,任选一个 $x$ 未被加入 $M$ 中的儿子 $u$,将 $u$ 加入 $M$ 并将 $x$ 改为 $u$。

每个 ddm 过程都会对应一个 ddm 序,一个 ddm 序是一个 $1\sim n$ 的排列 $p$,其中 $p_i$ 表示在对应的 ddm 过程中,节点 $i$ 是第 $p_i$ 个加入 $M$ 的。显然,对于树 $T$,可能会有很多不同的 ddm 过程,自然也对应很多不同的 ddm 序。

考完后,大D米发现真实的排名表是一个 $1\sim n$ 的排列 $a$。根据大D米的分析,这是由于考试的随机性保证的。为了圆回去,你需要找到这棵树的一个合法 ddm 序 $p$,使得 $a$ 能通过以下方式生成:

  • 初始令 $b=p$。
  • 进行任意次操作直到 $b=a$:
    • 任选 $x\ne 1$ ,使得 $b[\mathrm{fa}[x]] < b[x]$,然后交换 $b[\mathrm{fa}[x]]$ 和 $b[x]$。

对于某些排列 $a$,可能会出现没有合法 ddm 序的情况,这时候你需要报告无解。

输入格式

第一行一个整数 $tp$,表示测试点所在的测试包编号。

第二行一个整数 $n$,表示树 $T$ 的点数。

第三行 $n$ 个整数,第 $i$ 个整数表示 $a_i$。

第四行 $n-1$ 个整数,第 $i$ 个整数表示 $\mathrm{fa}[i+1]$ ,即 $i+1$ 的父亲。

输出格式

如果存在合法的 ddm 序 $p$,输出一行 $n$ 个整数,第 $i$ 个整数表示 $p_i$(即节点 $i$ 在对应 ddm 过程中是第 $p_i$ 个加入 $M$ 的)。如果有多个合法的 $p$,你可以任意输出一个。

否则,你只需要输出一行 -1

样例一

input

1
5
5 3 1 2 4
1 2 2 1

output

1 2 3 4 5

explanation

记交换 $b[\mathrm{fa}[x]],b[x]$ 的操作为 swap(fa[x],x)

一种可行的构造 $a$ 的方案是: swap(2,4), swap(1,2), swap(1,5), swap(2,3)

样例二

input

1
8
8 3 5 7 1 2 4 6
1 1 1 3 1 3 4

output

1 3 4 7 5 2 6 8 

样例三

见附加文件中 ex_tree3.inex_tree3.out,该组样例满足子任务 2 的性质。

样例四

见附加文件中 ex_tree4.inex_tree4.out,该组样例满足子任务 3 的性质。

样例五

见附加文件中 ex_tree5.inex_tree5.out,该组样例满足子任务 4 的性质。

限制与约定

对于 $100\%$ 的数据, $1\le n\le 10^5,1\le \mathrm{fa}[i] < i$ ,且保证 $a$ 是一个 $1\sim n$ 的排列。

子任务编号 $n\le$ 特殊性质 分值
$1$ $8$ $10$
$2$ $2000$ A $20$
$3$ B $15$
$4$ $15$
$5$ $10^5$ A $15$
$6$ B $15$
$7$ $10$

特殊性质 A :令当 $x$ 有多个儿子可选择作为 $u$ 时选择编号最小的策略的 ddm 过程对应 ddm 序 $p_0$,那么有解当且仅当 $p_0$ 合法。

特殊性质 B :至多只有一个点的儿子个数 $= 2$ ,且不存在儿子个数 $>2$ 的点。换句话说,树 $T$ 的形态形如 “倒 Y” 形。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$