← 返回题目列表

AtCoder · apc001_h

H. 广义插入排序

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

分数: 2000 点

问题陈述

你得到了一棵有根的树 N 顶点。 顶点已编号 0, 1, ..., N-1。 根是顶点 0,以及 Vertex 的父级 i (i = 1, 2, ..., N-1) 是顶点 p_i.

最初是一个整数 a_i 用 Vertex 编写 i。 在这里, (a_0, a_1, ..., a_{N-1}) 是一个排列 (0, 1, ..., N-1).

最多可以执行以下操作 25 000 次。这样做,以便将值写入 Vertex i 变为 i.

  • 选择一个顶点并调用它 v。考虑连接顶点的路径 0 和 v.
  • 旋转路径上写入的值。也就是说,对于每条边 (i, p_i) 沿着路径,替换Vertex中写入的值 p_i 将值写入 Vertex i (就在此操作之前),并替换 v 将值写入 Vertex 0 (就在此操作之前)。
  • 您可以选择顶点 0,在这种情况下该操作不执行任何操作。

约束

  • 2 \leq N \leq 2000
  • 0 \leq p_i \leq i-1
  • (a_0, a_1, ..., a_{N-1}) 是一个排列 (0, 1, ..., N-1).

输入

输入由标准输入按以下格式给出:

N
p_1 p_2 ... p_{N-1}
a_0 a_1 ... a_{N-1}

输出

在第一行中,打印操作数, Q。 在第二次通过 (Q+1)第行,按顺序打印所选顶点。


示例输入 1

5
0 1 2 3
2 4 0 1 3

示例输出 1

2
3
4
  • 第一次操作后,写入 Vertex 的值 0, 1, .., 4 是 4, 0, 1, 2, 3.

示例输入 2

5
0 1 2 2
4 3 1 2 0

示例输出 2

3
4
3
1
  • 第一次操作后,写入 Vertex 的值 0, 1, .., 4 是 3, 1, 0, 2, 4.
  • 第二次操作后,写入Vertex的值 0, 1, .., 4 是 1, 0, 2, 3, 4.