← 返回题目列表

Codeforces · 1783/G

G. 称重树木半径

中文机器翻译题面 查看原题

给你一棵由 $$$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$$$: