以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. First day
Moscow, March 7th, 2025
Problem Iron. Dreaming is not harmful
Input file: input.txt or standard input
Output file: output.txt or 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 suspended tree with the root at vertex number 1. The immediate
supervisor of employee number v is the employee with number pv. The level of competence of employee
v is defined by the parameter sv. 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 vk 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, q (2 ≤n ≤300 000, 1 ≤q ≤n) — the number of employees and the
number of queries.
The second line contains n −1 integers p2, p3, . . ., pn (1 ≤pi < i) — the immediate supervisors of
employees numbered from 2 to n.
The third line contains n integers s1, s2, . . ., sn (1 ≤si ≤n) — the levels of competence of the employees.
It is guaranteed that they are all different.
The fourth line contains q integers v1, v2, . . . , vq (1 ≤vi ≤n) — the promotion queries. It is guaranteed
that all numbers vi are distinct.
Output
Output q integers separated by spaces — the minimum number of days after which employees v1, v2, . . . , vq
can become directors.
Example
input output
5 4 1 3 0 2
1 2 2 1
3 5 1 2 4
5 3 1 4
Page 6 of 9
Open Olympiad in Informatics 2024/25. First day
Moscow, March 7th, 2025
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:
1 5
2 5 2
3 4 3 4
Initial structure Day 1
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:
1
2 4 3
2 5
3 4 5 3 5 5
3 4
Initial structure Day 1 Day 2 Day 3
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.
Page 7 of 9
Open Olympiad in Informatics 2024/25. First day
Moscow, March 7th, 2025
Additional constraints Required
Group Points Comment
Groups n q
0 0 – – – Examples.
1 10 – – – pi = 1 or pi = i −1, with pi = 1 for no
more than two numbers i
2 6 – – 1 pi = 1 or pi = i −1
3 8 n ≤50 q ≤50 0
4 13 n ≤1000 q ≤1000 0, 3
5 11 – q ≤100 0, 3
6 9 – – – pi = ⌊i2⌋
7 11 – – 0, 3, 6 The number of supervisors* for any
employee does not exceed 100
8 14 – – – si > spi 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.
Page 8 of 9