题目描述

小 Y 有一棵 $n$ 个点的树。树上编号为 $i$ 的点的权值为 $h_i$。

小 Y 还有 $k$ 枚棋子，其中第 $i$ 枚棋子初始时在编号为 $s_i$ 的点，小 Y 想把它移到编号为 $t_i$ 的点。

每一步小 Y 可以选择一枚棋子，然后将其移至与它当前所在顶点相邻的一个顶点。

定义一个状态的势能为每一枚棋子所在顶点的权值之和。如果一个顶点上有多枚棋子，则它的权值会被计算多次。

小 Y 想让过程中每一个状态（包括初始状态和结束状态）的势能的最大值最小，请你求出这个最小值。

输入格式

第一行一个整数 $n$（$1\le n\le 10^5$），表示树的点数。

第二行 $n$ 个整数 $h_1,h_2,\ldots,h_n$（$1\le h_i\le 10^9$），表示每个点的权值。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$（$1\le u_i,v_i\le n$），表示第 $i$ 条边连接的两个顶点。保证给出的图是一个树。

下一行一个整数 $k$（$1\le k\le 10^5$），表示棋子的数量。

接下来 $k$ 行，每行两个整数 $s_i,t_i$（$1\le s_i,t_i\le n$），表示第 $i$ 枚棋子的初始位置和结束位置。

输出格式

一个整数，即所求的答案。

样例

样例输入 1

3
1 3 2
1 2
2 3
2
1 3
3 1

样例输出 1

4

样例解释 1

一个最优的操作序列如下：

• 初始时，势能为 $3$。
• 将棋子 $2$ 移至顶点 $2$。势能变为 $4$。
• 将棋子 $2$ 移至顶点 $1$。势能变为 $2$。
• 将棋子 $1$ 移至顶点 $2$。势能变为 $4$。
• 将棋子 $1$ 移至顶点 $3$。势能变为 $3$。

样例输入 2

7
100 101 1 100 101 1 1000
1 2
2 3
4 5
5 6
1 7
4 7
2
1 3
4 6

样例输出 2

201

样例输入 3

5
2 1 100 5 6
1 2
2 3
3 4
3 5
2
2 2
4 5

样例输出 3

101

样例输入 4

4
1 2 3 100
1 4
2 4
3 4
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

样例输出 4

115

样例输入 5

6
1 100 1 1 10 1000
1 2
2 3
4 5
1 6
4 6
3
1 3
5 5
5 5

样例输出 5

102

子任务

• Subtask 1（30 points）： $n,k\le 50$。
• Subtask 2（40 points）： $n,k\le 2000$。
• Subtask 3（30 points）： 无额外限制。