P3682 [CERC2016] Free Figurines

Russian nesting dolls are wooden figurines of strictly increasing sizes that can be nested inside one another. Each figurine can be put into a larger figurine, and can itself contain a smaller figurine. At most one figurine can be directly nested inside any figurine, but that inner figurine can itself contain another, and so on. Given $n$ figurines with distinct sizes, they are numbered $1$ to $n$ in increasing order of size. If figurine $a$ is directly nested inside figurine $b$, then we say $b$ is the parent of $a$. If a figurine has no parent, we say it is free. A nesting configuration can be represented by specifying the parent of each figurine. In each step, you may perform exactly one of the following two operations: 1. Take a free figurine and directly place it into a larger figurine that currently contains nothing. 2. Choose a figurine that is not free (i.e., has a parent) and remove it from its parent. Given the initial configuration, compute the minimum number of steps to reach the target configuration.

The first line contains a positive integer $n(1 \le n \le 100000)$, the number of figurines. The second line contains $n$ integers $p_1,p_2,...,p_n(0 \le p_i \le n)$, giving the parent of each figurine in the initial configuration, where $0$ denotes a free figurine. The third line contains $n$ integers $q_1,q_2,...,q_n(0 \le q_i \le n)$, giving the parent of each figurine in the target configuration, where $0$ denotes a free figurine. The input guarantees that both the initial and the target configurations are valid.

Output a single integer, the minimum number of operations.

Translated by ChatGPT 5