Тропы Сулайман-Тоо


Отправить решение Решать в редакторе

Сложность: 60%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Священная гора Сулайман-Тоо в центре Оша — первый объект Всемирного наследия ЮНЕСКО в Кыргызстане. Её склоны покрыты сетью туристических троп, которые соединяют 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 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.