Codeforces Round 362 (Div. 1) |
---|
Закончено |
Барни ищет девушку своей мечты. Он живет в Нью-Йорке, который состоит из n перекрестков с номерами от 1 до n, соединенных n - 1 дорогами. Будем рассматривать Нью-Йорк как ориентированное дерево с корнем в перекрестке 1. В Нью-Йорке живут m девушек, i-я из них живет рядом с перекрестком номер ci, а ее вес исходно равен i килограмм.
Барни считает, что девушка x лучше девушки y тогда и только тогда, когда: вес девушки x строго меньше веса девушки y, либо же они весят одинаково, но номер перекрестка, рядом с которым живет девушка x строго меньше соответствующего номера для девушки y, то есть cx < cy. Таким образом, среди любой пары девушек одна из них всегда лучше другой.
В следующие q дней происходит по одному событию в день. Всего типов событий два:
Ваша задача — для каждого события первого типа сообщить Барни номера девушек, которых он пригласит к себе домой во время этого события.
Первая строка входных данных содержит три целых числа 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 в порядке от лучшей к худшей по меркам Барни.
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
В первом примере из условия:
Описание событий:
Название |
---|