Dreaming_is_not_harmful — OOI final
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 18
Algorithms: tree decomposition, sorting, path queries, tree

# Dreaming is not harmful

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 2 seconds       |
| Memory limit: | 256 megabytes   |

In the wedding agency M., mass layoffs are planned. All employees are busy counting the days until, with a favorable turn of events, they can head the company instead of working.

The structure of the company represents a rooted tree with the root at vertex number 1. The immediate supervisor of employee number $v$ is the employee with number $p_v$. The level of competence of employee $v$ is defined by the parameter $s_v$. This parameter is different for all employees. The higher the level of competence, the more useful the employee is to the company. Note that as a result of an opaque hiring process, it may happen that a less competent employee is the supervisor of a more competent one.

As a result of significant personnel restructuring, every day the CEO, who is at the root of the working hierarchy, will be fired. If there are employees left in the company, the most competent immediate subordinate will take their place. After that, the other subordinates of the former director will become subordinates of the new director. See the explanations in the examples for a better understanding of the condition.

Each employee easily calculated how many days it would take for them to become the CEO. Many were not ready to wait that long, as they would only get to be the director for one day! To speed up this process, they are ready to "cancel" one of their colleagues. The "canceled" employee's level of competence drops to 0, as no one is willing to interact with them anymore.

You will need to answer $q$ queries. In the $k$-th query, employee number $v_k$ is interested in the minimum number of days until they can head the company if they are willing to "cancel" exactly one employee. All queries are imaginary and independent, and the real levels of competence of the employees remain unchanged for all queries.

### Input

The first line contains two integers $n$ and $q$ ($2 \le n \le 300\,000$, $1 \le q \le n$) — the number of employees and the number of queries.

The second line contains $n - 1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) — the immediate supervisors of employees numbered from 2 to $n$.

The third line contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le n$) — the levels of competence of the employees. It is guaranteed that they are all different.

The fourth line contains $q$ integers $v_1, v_2, \dots, v_q$ ($1 \le v_i \le n$) — the promotion queries. It is guaranteed that all numbers $v_i$ are distinct.

### Output

Output $q$ integers separated by spaces — the minimum number of days after which employees $v_1, v_2, \dots, v_q$ can become directors.

### Example

| standard input          | standard output |
|-------------------------|-----------------|
| `5 4`                   | `1 3 0 2`         |
| `1 2 2 1`               |                 |
| `3 5 1 2 4`               |                 |
| `5 3 1 4`               |                 |

### Note

In the test example, the fifth employee can head the company in 1 day. To do this, it is enough to "cancel" the second employee. The structure of the company will change as follows:

![](_page_1_Figure_2.jpeg)

The third employee can head the company in 3 days. To do this, it is enough to "cancel" the fifth or fourth employee. If the fifth is canceled, the structure of the company will change as follows:

![](_page_1_Figure_4.jpeg)

The first employee is already the head of the company, so the answer to the corresponding query is 0. The fourth employee can become the head of the company in two days. It is enough, similarly to the previous example, to "cancel" the fifth employee.

### Scoring

The tests for this problem consist of nine groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed. Please note that passing the example tests is not required for some groups. Offline-evaluation means that the results of testing your solution on this group will only be available after the end of the competition.

The table with the groups is on the next page.

| Group | Points | Additional constraints |   | Required Groups | Comment                                                                |
|-------|--------|------------------------|---|-----------------|------------------------------------------------------------------------|
|       |        | $n$                      | $q$ |                 |                                                                        |
| 0     | 0      | -                      | - | -               | Examples.                                                              |
| 1     | 10     | -                      | - | -               | $p_i = 1$ or $p_i = i - 1$, with $p_i = 1$ for no more than two numbers $i$ |
| 2     | 6      | -                      | - | 1               | $p_i = 1$ or $p_i = i - 1$                                             |
| 3     | 8      | $n \le 50$             | $q \le 50$           | 0               |                                                                        |
| 4     | 13     | $n \le 1000$           | $q \le 1000$         | 0, 3            |                                                                        |
| 5     | 11     | -                      | $q \le 100$          | 0, 3            |                                                                        |
| 6     | 9      | -                      | - | -               | $p_i = \lfloor \frac{i}{2} \rfloor$                                    |
| 7     | 11     | -                      | - | 0, 3, 6          | The number of supervisors* for any employee does not exceed 100       |
| 8     | 14     | -                      | - | -               | $s_i > s_{p_i}$ for any $i > 1$                                        |
| 9     | 18     | -                      | - | 0 – 8           | Offline-evaluation.                                                    |

Supervisors* of an employee — the set of their immediate supervisor and all supervisors of their immediate supervisor.

Starter code: