/ 
Time Limit: 3 sec / Memory Limit: 256 MB
配点 : 2000 点
問題文
N 頂点の根つき木が与えられます。 頂点には番号 0, 1, ..., N-1 がついており、根は頂点 0 です。 そして、頂点 i(i = 1, 2, ..., N-1) の親は頂点 p_i です。
はじめ、頂点 i には整数 a_i が書かれています。 なお、(a_0, a_1, ..., a_{N-1}) は (0, 1, ..., N-1) の順列になっています。
あなたは以下の操作を 25,000 回まで好きな回数実行できます。頂点 i に書かれた値が i となるようにしてください。
- 頂点を 1 個選び v とする。頂点 0 と頂点 v の間のパスを考える。
- パス上の頂点の値を回転させる。つまり、パス上の各辺 (i, p_i) について、頂点 p_i に書かれた値を頂点 i に(この操作の直前に)書かれていた値に書き換え、頂点 v の値は頂点 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}
出力
1 行目に操作の回数 Q を出力せよ。 2 行目から Q+1 行目には、操作で選んだ頂点を順に出力せよ。
入力例 1
5 0 1 2 3 2 4 0 1 3
出力例 1
2 3 4
- 1 回目の操作後、頂点 0, 1, .., 4 に書かれた値は 4, 0, 1, 2, 3 となる
入力例 2
5 0 1 2 2 4 3 1 2 0
出力例 2
3 4 3 1
- 1 回目の操作後、頂点 0, 1, .., 4 に書かれた値は 3, 1, 0, 2, 4 となる
- 2 回目の操作後、頂点 0, 1, .., 4 に書かれた値は 1, 0, 2, 3, 4 となる
Score : 2000 points
Problem Statement
You are given a rooted tree with N vertices. The vertices are numbered 0, 1, ..., N-1. The root is Vertex 0, and the parent of Vertex i (i = 1, 2, ..., N-1) is Vertex p_i.
Initially, an integer a_i is written in Vertex i. Here, (a_0, a_1, ..., a_{N-1}) is a permutation of (0, 1, ..., N-1).
You can execute the following operation at most 25 000 times. Do it so that the value written in Vertex i becomes i.
- Choose a vertex and call it v. Consider the path connecting Vertex 0 and v.
- Rotate the values written on the path. That is, For each edge (i, p_i) along the path, replace the value written in Vertex p_i with the value written in Vertex i (just before this operation), and replace the value of v with the value written in Vertex 0 (just before this operation).
- You may choose Vertex 0, in which case the operation does nothing.
Constraints
- 2 \leq N \leq 2000
- 0 \leq p_i \leq i-1
- (a_0, a_1, ..., a_{N-1}) is a permutation of (0, 1, ..., N-1).
Input
Input is given from Standard Input in the following format:
N
p_1 p_2 ... p_{N-1}
a_0 a_1 ... a_{N-1}
Output
In the first line, print the number of operations, Q. In the second through (Q+1)-th lines, print the chosen vertices in order.
Sample Input 1
5 0 1 2 3 2 4 0 1 3
Sample Output 1
2 3 4
- After the first operation, the values written in Vertex 0, 1, .., 4 are 4, 0, 1, 2, 3.
Sample Input 2
5 0 1 2 2 4 3 1 2 0
Sample Output 2
3 4 3 1
- After the first operation, the values written in Vertex 0, 1, .., 4 are 3, 1, 0, 2, 4.
- After the second operation, the values written in Vertex 0, 1, .., 4 are 1, 0, 2, 3, 4.