G. Радиус взвешенного дерева
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано дерево из $$$n$$$ вершин и $$$n - 1$$$ ребра. Первоначальный вес $$$i$$$-й вершины равен $$$a_i$$$.

Назовем расстоянием $$$d_v(u)$$$ от вершины $$$v$$$ до вершины $$$u$$$ количество ребер на пути из $$$v$$$ в $$$u$$$. Заметим, что $$$d_v(u) = d_u(v)$$$ и $$$d_v(v) = 0$$$.

Назовем взвешенным расстоянием $$$w_v(u)$$$ от $$$v$$$ до $$$u$$$ значение $$$w_v(u) = d_v(u) + a_u$$$. Заметим, что $$$w_v(v) = a_v$$$ и $$$w_v(u) \neq w_u(v)$$$, если $$$a_u \neq a_v$$$.

Аналогично обычному расстоянию, назовем эксцентриситетом $$$e(v)$$$ вершины $$$v$$$ наибольшее взвешенное расстояние от $$$v$$$ до какой-либо вершины (включая саму $$$v$$$), или $$$e(v) = \max\limits_{1 \le u \le n}{w_v(u)}$$$.

Наконец, назовем радиусом $$$r$$$ дерева наименьший из эксцентриситетов его вершин, или $$$r = \min\limits_{1 \le v \le n}{e(v)}$$$.

Вам нужно обработать $$$m$$$ запросов следующего вида:

  • $$$v_j$$$ $$$x_j$$$ — присвоить $$$a_{v_j} = x_j$$$.

После обработки каждого запроса выведите радиус $$$r$$$ текущего дерева.

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

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — первоначальные веса вершин.

В следующих $$$n - 1$$$ строках заданы ребра дерева. В $$$i$$$-й строке заданы два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — соответствующее ребро. Заданные ребра образуют дерево.

В следующей строке задано одно целое число $$$m$$$ ($$$1 \le m \le 10^5$$$) — количество запросов.

В следующих $$$m$$$ строках заданы сами запросы — по одному в строке. В $$$j$$$-м запросе заданы два целых числа $$$v_j$$$ и $$$x_j$$$ ($$$1 \le v_j \le n$$$; $$$0 \le x_j \le 10^6$$$) — вершина и ее новый вес.

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

Выведите $$$m$$$ целых чисел — радиус $$$r$$$ дерева после обработки каждого запроса.

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

После первого запроса дерево выглядит следующим образом:

Цветом на изображении отмечена вершина с наименьшим $$$e(v)$$$, соответственно $$$r = e(4) = 7$$$. Эксцентриситеты других вершин равны: $$$e(1) = 8$$$, $$$e(2) = 9$$$, $$$e(3) = 9$$$, $$$e(5) = 8$$$, $$$e(6) = 8$$$.

Дерево после второго запроса:

Радиус $$$r = e(1) = 4$$$.

После третьего запроса радиус $$$r = e(2) = 5$$$: