给你一棵由 $$$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$$$ 且 $$$w_v(u) \neq w_u(v)$$$ 如果 $$$a_u \neq a_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$$$。
输入
第一行包含单个整数 $$$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$$$。
示例
输入 #1
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
输出 #1
7 4 5 10 7
注意
第一次查询后,您将得到以下树:
第二次查询后的树:
第三次查询后,半径$$$r = e(2) = 5$$$: