Олимпиадный тренинг

Задача . G. Радиус взвешенного дерева

Задача

Темы: Деревья разделяй и властвуй реализация Структуры данных *2800

Вам задано дерево из $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$ дерева после обработки каждого запроса.

Примечание

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

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

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