Generalized Insertion Sort

AtCoder

IDapc001_h

Time3000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

5
0 1 2 3
2 4 0 1 3

Output #1

2
3
4

*   After the first operation, the values written in Vertex $0, 1, .., 4$ are $4, 0, 1, 2, 3$.

Input #2

5
0 1 2 2
4 3 1 2 0

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$.

API Response (JSON)

{
  "problem": {
    "name": "Generalized Insertion Sort",
    "description": {
      "content": "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 in",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "apc001_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$.\nInitially, an in...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments