题目描述

王老师要经常进行淘汰旅行，他所在的城市有 N 个学校，标号为1, 2, 3，…, N，这 N 个学校由 n - 1 条路连接，构成一棵树。每个学校可以加入或淘汰学生，同一学校加入学生的舒适度和淘汰学生的舒适度为相反数，王老师想从学校 a 走到学校 b，在这过程中，在某个学校加入一个学生，然后在一个学校淘汰，可以是同一学校加入和淘汰，使得舒适度最大，注意不能走回头路。

输入格式

第一行一个数 N，第二行 N 个数，第 i 个数表示学校 i 淘汰学生的舒适度。
接下来 N – 1 行，每行两个数 a, b,表示学校 a 到学校 b 之间有一条双向的道路。
接下一行一个数 Q，表示有 Q 个询问，接下来 Q 行，每行两个数 x，y，表示要求王老师从学校 x 到学校 y 的最大舒适度。

输出格式

对于每个询问，给出一个答案，各占一行。

样例输入

10
16 5 1 15 15 1 8 9 9 15 
1 2
1 3
2 4
2 5
2 6
6 7
4 8
1 9
1 10
6
9 1
5 1
1 7
3 3
1 1
3 6

样例输出

7
11
7
0
0
15

数据范围

对于 50%的数据，0 < n <= 1000,0 < m <= 100
对于 100%的数据，0 < n <= 100000,0 < m <= 10000，0 <= 淘汰的舒适度 <= 10^8

限制

1s

来源

CWOI新高二专题测试十一