Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | qual.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | qual.out | |||
Максимальный балл: | 100 |
Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают n сотрудников. Каждому сотруднику присвоен уникальный номер от 1 до n, директору присвоен номер 1. У каждого сотрудника, кроме директора, есть ровно один непосредственный начальник. Непосредственный начальник сотрудника i имеет номер pi , причем pi < i.
Сотрудник x является подчиненным уровня 1 сотрудника y, если px = y. Для k > 1 сотрудник x является подчиненным уровня k сотрудника y, если сотрудник px является подчиненным уровня k − 1 сотрудника y.
У директора компании появилась возможность направить некоторых сотрудников на курсы повышения квалификации. Для этого он решил выбрать два числа L и R и направить на курсы всех сотрудников с номерами i, такими что L ≤ i ≤ R.
Перед тем, как выбрать числа L и R, директор получил m пожеланий от сотрудников компании, j-е пожелание задается двумя числами uj и kj и означает, что сотрудник uj просит отправить на курсы одного из своих подчиненных уровня kj. Для экономии средств директор хочет выбрать такие L и R, чтобы количество сотрудников, направленных на повышение квалификации, было минимальным возможным, но при этом все пожелания были выполнены.
Требуется написать программу, которая по заданным в компании отношениям начальник-подчиненный и пожеланиям сотрудников определяет такие числа L и R, что если отправить на курсы повышения квалификации всех сотрудников с номерами от L до R включительно, то все пожелания будут выполнены, а количество сотрудников, направленных на повышение квалификации, будет минимальным возможным. Если оптимальных пар чисел L, R будет несколько, требуется найти ту из них, в которой значение L минимально.
Первая строка входного файла содержит число n — количество сотрудников компании. Вторая строка содержит (n − 1) чисел: p2, p3, …, pn (1 ≤ pi ≤ i) — номера непосредственных начальников сотрудников.
Третья строка содержит число m — количество пожеланий от сотрудников.
Последующие m строк задают пожелания сотрудников и содержат по два целых числа uj, kj (1 ≤ uj < n, 1 ≤ kj < n, гарантируется, что у сотрудника uj есть хотя бы один подчиненный уровня kj).
Необходимо вывести два искомых числа: L и R. Если оптимальных пар (L, R) несколько, требуется вывести ту, в которой значение L минимально.
2 ≤ n, m ≤ 200 000
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | |
---|---|---|---|---|
n | Дополнительные условия | |||
1 | 19 | 2 ≤ n, m ≤ 50 | ||
2 | 25 | 2 ≤ n, m ≤ 3000 | 1 | |
3 | 21 | 2 ≤ n, m ≤ 200 000 | для всех i выполнено pi = i − 1 | |
4 | 35 | 2 ≤ n, m ≤ 200 000 | 1, 2, 3 |
По запросу сообщаются баллы за каждую подзадачу.
На повышение квалификации будут направлены сотрудники с номерами 3, 4, 5 и 6. Сотрудник с номером 3 является подчиненным уровня 1 сотрудника с номером 1, сотрудник с номером 4 — подчиненным уровня 2 сотрудника с номером 1, а сотрудник с номером 6 — подчиненным уровня 1 сотрудника с номером 3.
№ | Входной файл (qual.in ) |
Выходной файл (qual.out ) |
---|---|---|
1 |
|
|