硕哥的树贸易

硕哥的树贸易

测试数据来自 nnu_contest/1098

描述

有一张n个点的树,点的标号是1~n,第i个点的点权为wi。Q次询问,每次询问两个点,求在这两点间的最短路径上完成一次贸易的最大利润(在一个点买入价格为其点权的商品,在后面的一个点卖出)。输入中第一行为n,后面n行,每行一个数为每个点的点权,后面n-1行,每行两个数a,b,表示一条树边(a,b),接下来单行输入一个数为Q,后面Q行,每行两个数表示路径的起点和终点。

输入样例

4
1 
5 
3 
2
1 3
3 2
3 4
9
1 2
1 3
1 4
2 3
2 1
2 4
3 1
3 2
3 4

输出样例

4
2
2
0
0
0
0
2
0

样例解释

对于第一个询问,在一号点以1的价格买入,在二号点以5的价格卖出,获利为4。
后面的询问以此类推。

时空限制

每个测试点1s
空间65536KB

数据范围

对于100%的数据,满足1<=n,Q,wi<=50000

信息

ID
1391
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者