Weighed Tree Radius
Contest: Educational Codeforces Round 141 (Rated for Div. 2)
Difficulty rating: 2800
Tags: data structures, divide and conquer, implementation, trees

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.

Input format:
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.

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

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
After the first query, you have the following tree:

The tree after the second query:

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

Example input:
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

Example output:
7
4
5
10
7

Editorial:
Firstly, let's define the weight of path $$$(u, v)$$$ as $$$w_p(u, v) = a_u + d_u(v) + a_v$$$. On contrary to weighted distances, $$$w_p(u, v) = w_p(v, u)$$$ and also $$$w_p(v, v) = 2 a_v$$$.
Now, let's define the diameter of a tree as path $$$(u, v)$$$ with maximum $$$w_p(u, v)$$$. It's okay if diameter may be explicit case $$$(v, v)$$$. The useful part of such definition is next: our diameter still holds most properties of the usual diameter. Let's look at two of them:
• There is a vertex on diameter path $$$(x, y)$$$ with $$$w_v(x) = \left\lceil \frac{w_p(x, y)}{2} \right\rceil$$$ and $$$w_v(y) = w_p(x, y) - w_v(x)$$$. It's easy to prove after noting the fact that $$$a_x \le d_x(y) + a_y$$$ and $$$a_y \le d_y(x) + a_x$$$ (otherwise, you could choose diameter $$$(x, x)$$$ or $$$(y, y)$$$).
• For any vertex $$$v$$$ eccentricity $$$e(v) = \max(w_v(x), w_v(y))$$$. In other words, either $$$x$$$ or $$$y$$$ has the maximum distance from $$$v$$$. (You can also prove it by contradiction). It also means that $$$e(v) \ge \left\lceil \frac{w_p(x, y)}{2} \right\rceil$$$.
Now let's look how the diameter changes when we change the weight $$$a_v$$$. If $$$a_v$$$ is increasing it's quite easy. The only paths that change weights are the paths ending at $$$v$$$. Denote such path as $$$(v, u)$$$ and note that either $$$v = u$$$ or $$$w_p(v, u) = a_v + w_v(u) \le a_v + e(v)$$$ $$$=$$$ $$$a_v + \max(w_v(x), w_v(y))$$$. In other words, there will be only three candidates for a new diameter:
1. path $$$(v, v)$$$ with $$$w_p(v, v) = 2 a_v$$$;
2. path $$$(v, x)$$$ with $$$w_p(v, x) = a_v + d_v(x) + a_x$$$;
3. path $$$(v, y)$$$ with $$$w_p(v, y) = a_v + d_v(y) + a_y$$$.
The only thing you need to calculate fast enough is the two distances $$$d_v(x)$$$ and $$$d_v(y)$$$. And since $$$d_v(x) = depth(v) + depth(x) - 2 \cdot depth(lca(v, x))$$$, your task is to calculate $$$lca$$$.
Finally, how to handle decreasing $$$a_v$$$'s? Let's get rid of them using DCP (dynamic connectivity problem) technique. Keep track of each value $$$a_v$$$: each possible value $$$a_v$$$ for some vertex $$$v$$$ will be "active" on some segment of queries $$$[l, r) \in [0, m)$$$. Since there are only $$$m$$$ queries, there will be exactly $$$n + m$$$ such segments for all vertices $$$v$$$ in total.
Now, all queries becomes "assign $$$a_v = x$$$ on some segment of queries $$$[l, r)$$$". Note that in that case, the previous value of $$$a_v$$$ was $$$0$$$, so you are dealing with only "increasing value" queries.
Finally, to handle all range queries efficiently, you build a Segment Tree on queries, set all queries and then traverse your Segment Tree while maintaining the current diameter in order to calculate answers for all queries.
Each of $$$n + m$$$ queries transforms in $$$O(\log{m})$$$ queries to segment tree vertices, and preforming each query asks you to calculate $$$lca$$$ two times.
If you use the usual binary lifting, then your complexity becomes $$$O((n + m) \log{m} \log{n})$$$ what is okay. But if you use Sparse Table on Euler tour, you can take $$$lca$$$ in $$$O(1)$$$ and your complexity will be $$$O(n \log{n} + (n + m) \log{m})$$$.