#P13806. [apc001]Generalized Insertion Sort

    ID: 13007 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-序列构造插入排序树形 DP二分查找不变量分析直接模拟

[apc001]Generalized Insertion Sort

题目描述

给定一棵有 NN 个顶点的有根树。顶点编号为 0, 1, …, N−10,\ 1,\ \ldots,\ N-1,根为顶点 00。顶点 ii(i=1, 2, …, N−1i=1,\ 2,\ \ldots,\ N-1)的父节点为 pip_i。

初始时,每个顶点 ii 上写有一个整数 aia_i。(a0, a1, …, aN−1)(a_0,\ a_1,\ \ldots,\ a_{N-1}) 是 00 到 N−1N-1 的一个排列。

你可以最多进行 2500025000 次如下操作,从而使得每个顶点 ii 上的值变为 ii。

  • 选择一个顶点 vv。考虑从顶点 00 到顶点 vv 的路径。
  • 将这条路径上的顶点的值按从根到 vv 的顺序循环左移。具体而言,路径上每个非根顶点 ii 原有的值移到其父节点 pip_i,而根顶点 00 原有的值移到 vv。所有移动同时进行。
  • 你也可以选择顶点 00,但在这种情况下,这个操作什么也不做。

输入格式

输入从标准输入读入,格式如下:

NN p1p_1 p2p_2 ... pN−1p_{N-1} a0a_0 a1a_1 ... aN−1a_{N-1}

输出格式

第一行输出操作次数 QQ。
接下来的 QQ 行,每行输出一次操作中选择的顶点编号。

输入输出样例 #1

输入 #1

5
0 1 2 3
2 4 0 1 3

输出 #1

2
3
4

输入输出样例 #2

输入 #2

5
0 1 2 2
4 3 1 2 0

输出 #2

3
4
3
1

说明/提示

约束条件

  • 2≤N≤20002 \leq N \leq 2000
  • 0≤pi≤i−10 \leq p_i \leq i-1
  • (a0, a1, …, aN−1)(a_0,\ a_1,\ \ldots,\ a_{N-1}) 是 00 到 N−1N-1 的一个排列

样例说明 1

  • 第 11 次操作后,顶点 0, 1, …, 40,\ 1,\ \ldots,\ 4 上的值分别变为 4, 0, 1, 2, 34,\ 0,\ 1,\ 2,\ 3。

样例说明 2

  • 第 11 次操作后,顶点 0, 1, …, 40,\ 1,\ \ldots,\ 4 上的值分别变为 3, 1, 0, 2, 43,\ 1,\ 0,\ 2,\ 4。
  • 第 22 次操作后,顶点 0, 1, …, 40,\ 1,\ \ldots,\ 4 上的值分别变为 1, 0, 2, 3, 41,\ 0,\ 2,\ 3,\ 4。