Олимпиадный тренинг

Задача . E. ...Подожди...


Задача

Темы: Деревья снм Структуры данных *3000

Барни ищет девушку своей мечты. Он живет в Нью-Йорке, который состоит из n перекрестков с номерами от 1 до n, соединенных n - 1 дорогами. Будем рассматривать Нью-Йорк как ориентированное дерево с корнем в перекрестке 1. В Нью-Йорке живут m девушек, i-я из них живет рядом с перекрестком номер ci, а ее вес исходно равен i килограмм.

Барни считает, что девушка x лучше девушки y тогда и только тогда, когда: вес девушки x строго меньше веса девушки y, либо же они весят одинаково, но номер перекрестка, рядом с которым живет девушка x строго меньше соответствующего номера для девушки y, то есть cx < cy. Таким образом, среди любой пары девушек одна из них всегда лучше другой.

В следующие q дней происходит по одному событию в день. Всего типов событий два:

  1. Барни идет от перекрестка v до перекрестка u. На пути он подбирает не более k лучших девушек, которых он еще не приглашал и приглашает к себе домой, чтобы проверить, не является ли кто-то из них девушкой его мечты. Если на пути Барни находятся меньше чем k еще не приглашенных девушек, то Барни приглашает их всех.
  2. Девушки, живущие возле перекрестков в поддереве перекрестка v (включая сам перекресток v) набирают вес. В результате вес каждой из них увеличивается на k килограмм.

Ваша задача — для каждого события первого типа сообщить Барни номера девушек, которых он пригласит к себе домой во время этого события.

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

Первая строка входных данных содержит три целых числа n, m and q (1 ≤ n, m, q ≤ 105) — количество перекрестков в Нью-Йорке, количество девушек, живущих в Нью-Йорке и количество событий соответственно.

Следующие n - 1 строк описывают дороги. Каждая строка содержит два целых числа v и u(1 ≤ v, u ≤ n, v ≠ u) означающих существование дороги между перекрестками v and u.

Следующая строка содержит m целых чисел c1, c2, ..., cm (1 ≤ ci ≤ n) — перекрестки рядом с домами девушек.

Следующие q строк описывают события в хронологическом порядке. Каждая строка начинается с целого числа t (1 ≤ t ≤ 2) — типа события.

Если t = 1, то строка описывает событие первого типа и далее следуют три целых числа v, u и k (1 ≤ v, u, k ≤ n) — концы пути Барни и максимальное число девушек, которых он пригласит.

Иначе строка описывает событие второго типа и далее следуют два целых числа v и k (1 ≤ v ≤ n, 1 ≤ k ≤ 109) — корень поддерева и значение, на которое увеличатся веса всех девушек в этом поддереве.

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

Для каждого события первого типа выведите число t и t целых чисел g1, g2, ..., gt в одной строке, означающих, что во время этого события Барни пригласит t девушек, номера которых равны g1, ..., gt в порядке от лучшей к худшей по меркам Барни.

Примечание

В первом примере из условия:

Описание событий:

  1. Веса девушек в поддереве перекрестка 4 увеличиваются на 3. Номера этих девушек: 1, 3, 5, 4, 7.
  2. Барни идет от перекрестка 2 до перекрестка 1. На его пути встречаются девушки с номерами 1, 2, 3, 5, 6, 7 и весами 4, 2, 6, 8, 6, 10 соответственно. Он приглашает девушек 2 и 1.
  3. Барни идет от перекрестка 4 до перекрестка 2. На его пути встречаются девушки с номерами 3, 5, 7 и весами 6, 8, 10 соответственно. Барни приглашает девушку 3.
  4. Веса девушек в поддереве перекрестка 2 увеличиваются на 10. Неприглашенных девушек это не касается, и ничего интересного не происходит.
  5. Веса девушек в поддереве перекрестка 1 увеличиваются на 10. Номера этих девушек равны 4, 5, 6, 7.
  6. Барни идет от перекрестка 2 до перекрестка 4. На его пути встречаются девушки с номерами 5, 7 и весами 18, 20 соответственно. Барни приглашает девушку с номером 5.
  7. Барни идет от перекрестка 2 до перекрестка 3. На его пути нет девушек.
  8. Веса девушек в поддереве перекрестка 5 увеличиваются на 2. Единственная девушка там имеет номер 4.
  9. Веса девушек в поддереве перекрестка 4 увеличиваются на 9. Номера этих девушек: 4, 6, 7.
  10. Барни идет от перекрестка 3 до перекрестка 5. Единственная девушка на его пути имеет номер 4.
  11. Барни идет от перекрестка 1 до перекрестка 2. Девушки на его пути имеют номера 6, 7 и веса 16, 29 соответственно.

Примеры
№Входные данныеВыходные данные
1 5 7 11
3 5
2 3
4 3
1 4
4 1 4 5 4 1 4
2 4 3
1 2 1 2
1 4 2 1
2 2 10
2 1 10
1 2 4 1
1 2 3 4
2 5 2
2 4 9
1 3 5 2
1 1 2 3 
2 2 1
1 3
1 5
0
1 4
2 6 7

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет