Migrated from Lutece 3017 旅游规划

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A国家有 $n$ 个景点，编号从 $1$ 到 $n$。 有 $n-1$ 条道路，每条道路都连接这 $n$ 个景点中的某两个景点。保证可以图联通，即形成一个树结构。 每个景点都有一个愉悦值，第 $i$ 个景点的愉悦值为 $a_i$。如果一个人来到第 $i$ 个景点并且参观了这个景点，那么他可以获得 $a_i$ 的愉悦值。 一个人来A国旅游的愉悦值为参观过的所有景点的愉悦值之和。 但是，对于被某条道路直接相连的两个景点 $p$ 和 $q$，它们主打的卖点有诸多相似之处。因此，如果一个人已经参观过 $p$ 这个景点，然后参观 $q$ 这个景点，则他会感到非常无聊，他参观 $q$ 这个景点获得的愉悦值将变成-114514。 由于季节的变化和旅客口味的变化，一个景点的愉悦值可能发生变化。 当一次变化发生时，你需要告诉旅客，在本次变化生效后，一位旅客来A国旅游可以获得的最大愉悦值。

请注意：

1. 每一条道路都可以多次经过。
2. 对于一个景点，可以只路过而不参观。
3. 一个人来A国旅游可以总共参观 $0$ 个景点，此时愉悦值为 $0$。

Input

输入第一行包含一个整数 $n$。 第二行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$ 。 接下来 $n-1$ 行，每行有两个整数 $u,v$ ，表示存在一条道路连接了景点 $u$ 和景点 $v$。 接下来一行，包含一个整数 $m$，表示所有景点愉悦度变化的总次数。 接下来$m$行，每行包含两个整数 $u$ 和 $x$，表示景点 $u$ 的愉悦度变成了 $x$。

Output

输出包含 $m$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 次景点愉悦度变化发生后，一位旅客来A国旅游可以获得的最大愉悦值。

Samples

6
1 1 4 5 1 4
2 1
3 2
4 2
5 1
6 5
6
6 -5
4 -5
5 -5
1 -5
3 -5
2 -5

10
5
5
4
1
0

Constraints

$1\le n,m\le 10^5,-10^4\le x,a_i\le 10^4,1\le u,v\le n$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming