CF1783G.Weighed Tree Radius

You are given a tree of $n$ vertices and $n - 1$ edges. The $i$-th vertex has an initial weight $a_i$.

Let the distance $d_v(u)$ from vertex $v$ to vertex $u$ be the number of edges on the path from $v$ to $u$. Note that $d_v(u) = d_u(v)$ and $d_v(v) = 0$.

Let the weighted distance $w_v(u)$ from $v$ to $u$ be $w_v(u) = d_v(u) + a_u$. Note that $w_v(v) = a_v$ and $w_v(u) \neq w_u(v)$ if $a_u \neq a_v$.

Analogically to usual distance, let's define the eccentricity $e(v)$ of vertex $v$ as the greatest weighted distance from $v$ to any other vertex (including $v$ itself), or $e(v) = \max\limits_{1 \le u \le n}{w_v(u)}$.

Finally, let's define the radius $r$ of the tree as the minimum eccentricity of any vertex, or $r = \min\limits_{1 \le v \le n}{e(v)}$.

You need to perform $m$ queries of the following form:

• $v_j$ $x_j$ — assign $a_{v_j} = x_j$.

After performing each query, print the radius $r$ of the current tree.

给你一棵包含 $n$ 个顶点和 $n - 1$ 条边的树。第 $i$ 个顶点的初始权重为 $a_i$。

定义顶点 $v$ 到顶点 $u$ 的距离 $d_v(u)$ 为从 $v$ 到 $u$ 的路径上的边数。注意：$d_v(u) = d_u(v)$，且 $d_v(v) = 0$。

定义顶点 $v$ 到顶点 $u$ 的加权距离 $w_v(u)$ 为 $w_v(u) = d_v(u) + a_u$。注意：$w_v(v) = a_v$，且当 $a_u \neq a_v$ 时，有 $w_v(u) \neq w_u(v)$。

类比于通常的距离概念，定义顶点 $v$ 的离心率 $e(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$。

The first line contains the single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line contains $n$ integers $a_1, \dots, a_n$ ($0 \le a_i \le 10^6$) — the initial weights of vertices.

Next $n - 1$ lines contain edges of tree. The $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \neq v_i$) — the corresponding edge. The given edges form a tree.

The next line contains the single integer $m$ ($1 \le m \le 10^5$) — the number of queries.

Next $m$ lines contain queries — one query per line. The $j$-th query contains two integers $v_j$ and $x_j$ ($1 \le v_j \le n$; $0 \le x_j \le 10^6$) — a vertex and it's new weight.

第一行包含一个整数 $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$）——一个顶点及其新的权值。

Print $m$ integers — the radius $r$ of the tree after performing each query.

输出 $m$ 个整数——每次查询操作后树的半径 $r$。

After the first query, you have the following tree:

The marked vertex in the picture is the vertex with minimum $e(v)$, or $r = e(4) = 7$. The eccentricities of the other vertices are the following: $e(1) = 8$, $e(2) = 9$, $e(3) = 9$, $e(5) = 8$, $e(6) = 8$.

The tree after the second query:

The radius $r = e(1) = 4$.

After the third query, the radius $r = e(2) = 5$:

第一次查询后，你得到如下树：

图中标记的顶点是使 $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$：