Тропы Сулайман-Тоо
Священная гора Сулайман-Тоо в центре Оша — первый объект Всемирного наследия ЮНЕСКО в Кыргызстане. Её склоны покрыты сетью туристических троп, которые соединяют n смотровых площадок. Площадки пронумерованы от 1 до n, а тропы устроены так, что от любой площадки до любой другой можно дойти единственным способом, не проходя ни одну площадку дважды (то есть тропы образуют дерево).

Вершина Сулайман-Тоо. Фото: Adam Harangozó, CC BY-SA 4.0, Wikimedia Commons
У каждой площадки v есть высота над уровнем моря h[v]. Студент ОшГУ Айбек готовит путеводитель и хочет для любого маршрута быстро отвечать на вопрос: какая самая высокая точка встретится по пути и сколько площадок маршрута находятся ровно на этой высоте (с них открывается одинаково лучший вид).
Иногда геодезисты уточняют измерения, и высота площадки меняется.
Обработайте q запросов двух видов:
1 v x— высота площадкиvстановится равнойx;2 u v— рассмотрим маршрут из площадкиuв площадкуv(включая обе крайние площадки). Выведите максимальную высоту площадки на маршруте и количество площадок маршрута с такой высотой.
Входные данные
В первой строке — целое число n (1 ≤ n ≤ 200 000) — количество смотровых площадок.
Во второй строке — n целых чисел h[1], h[2], …, h[n] (1 ≤ h[i] ≤ 10⁹).
В каждой из следующих n − 1 строк — два числа a и b (1 ≤ a, b ≤ n, a ≠ b): площадки a и b соединены тропой. Гарантируется, что тропы образуют дерево.
Далее — число q (1 ≤ q ≤ 200 000), а затем q строк с запросами в описанном выше формате (1 ≤ u, v ≤ n, 1 ≤ x ≤ 10⁹). Площадки u и v в запросе могут совпадать.
Выходные данные
Для каждого запроса второго вида выведите в отдельной строке два числа: максимальную высоту на маршруте и количество площадок маршрута, имеющих эту высоту.
Пример 1
Вход:
6
3 7 2 7 5 1
1 2
2 3
2 4
4 5
4 6
5
2 3 5
2 3 6
1 3 9
2 3 6
2 6 6
Выход:
7 2
7 2
9 1
1 1
Пояснение
Маршрут 3 → 2 → 4 → 5 проходит через высоты 2, 7, 7, 5: максимум равен 7 и достигается дважды. После третьего запроса площадка 3 становится самой высокой точкой маршрута 3 → 2 → 4 → 6. Маршрут из площадки в саму себя состоит из одной площадки.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 15 | n, q ≤ 2000 |
| 2 | 20 | нет запросов первого вида |
| 3 | 20 | тропы соединяют только площадки i и i + 1 (гора — одна длинная тропа) |
| 4 | 45 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии