Задача №113706. Почтовая реформа
В Флатландии идет пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причем только одним способом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.
Недавно образованное почтовое агентство «Экс-Федя» предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h , курьеру агентства требуется иметь с собой не менее h метров веревки.
Вам поручено руководить отделом логистики — по имеющимся данным о высотах башен и об их изменениях вам нужно определять минимальную длину веревки, которую нужно выдать курьеру, который доставляет посылки между городами i и j .
Первая строка входного файла содержит число n — количество городов в Флатландии ( 1 ≤ n ≤ 50 000 ). Во второй строке находится n положительных чисел, не превосходящих 10 5 — высоты башен в городах. В следующих n - 1 строках содержится по два числа u i и v i — описание i -й дороги, 1 ≤ u i , v i ≤ n , u i ≠ v i . В следующий строке содержится число k — количество запросов ( 1 ≤ k ≤ 100 000 ). В следующих k строках содержатся описания запросов в следующем формате:
- Уведомление от волшебника из города i о том, что высота его башни стала равна h , имеет вид ! i h , 1 ≤ i ≤ n , 1 ≤ h ≤ 10 5 .
-
Запрос от курьера о выдаче веревки для доставки посылок во все города на пути от
i
до
j
включительно имеет вид
?
i
j
,
1 ≤
i
,
j
≤
n
.
Для каждого запроса доставки посылок выведите минимальную длину веревки, которую необходимо выдать курьеру.
20 баллов — ( 1 ≤ n, k ≤ 100) .
30 баллов — каждый город соединен дорогами не более чем с двумя другими.
50 баллов — полные ограничения.
3 1 2 3 1 3 2 3 5 ? 1 2 ! 1 5 ? 2 3 ! 3 2 ? 1 2
3 3 5
1 100 5 ! 1 1 ? 1 1 ! 1 1000 ? 1 1 ! 1 1
1 1000