Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Повышение квалификации

(Время: 3 сек. Память: 64 Мб Сложность: 75%)

Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают 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 минимально.

Входные данные

Первая строка входного файла INPUT.TXT содержит число n – количество сотрудников компании (2 ≤ n ≤ 200 000). Вторая строка содержит (n – 1) чисел: p2, p3, …, pn (1 ≤ pi < i) – номера непосредственных начальников сотрудников. Третья строка содержит число m (1 ≤ m ≤ 200 000) – количество пожеланий от сотрудников. Последующие m строк задают пожелания сотрудников и содержат по два целых числа uj , kj (1 ≤ uj < n, 1 ≤ kj < n, гарантируется, что у сотрудника uj есть хотя бы один подчиненный уровня kj).

Выходные данные

В выходной файл OUTPUT.TXT выведите два искомых числа: L и R. Если оптимальных пар (L, R) несколько, требуется вывести ту, в которой значение L минимально.

Пример

INPUT.TXTOUTPUT.TXT
17
1 1 2 2 3 3
3
1 1
3 1
1 2
3 6

Пояснение к примеру

На повышение квалификации будут направлены сотрудники с номерами 3, 4, 5 и 6. Сотрудник с номером 3 является подчиненным уровня 1 сотрудника с номером 1, сотрудник с номером 4 – подчиненным уровня 2 сотрудника с номером 1, а сотрудник с номером 6 – подчиненным уровня 1 сотрудника с номером 3.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 A. Кампус
 B. Калькулятор
 C. Размещение данных
 D. Полезные ископаемые
 E. Автоматизированное управление доставкой
 F. Большой линейный коллайдер
 G. Силовые поля
 H. Повышение квалификации

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483



Консультант онлайн для сайта лайн консультант на сайте www.salesup.helpkit.ru.