11300: 【原1300】businessman
题目
题目描述
author: 宋沁芸 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1300
Description
一个国家有N个城市，从1到N编号，并且满足任意两个城市之间只有一条简单路径。一个商人准备从某城市出发去某城市，并且在路上买入并且卖出商品最多一次赚取差价。商品在每个城市都是一样的，只是价格不一样。商人决定一共要走C条路径，于是请你帮他计算出对于每条路径，他的最大盈利是多少。需要注意的是，商人是不能经过一条边超过1次的！
Input Format
第一行有一个整数N，表示这个国家有N个城市。
第二行包含N个整数，表示商品在每个国家的价格。
接下来N-1行，每行两个正整数a，b，表示a和b之间有一条无向边，
接下来一个整数C，表示商人一共有C条路径。
接下来C行，每行两个正整数c，d，表示一条从c到d的路径。
Output Format
输出C行，对于每条路径商人能得到的最大盈利。
Sample Input
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
Sample Output
4
2
2
0
0
0
0
2
0
Range
20% 1 <= N, C <= 100;
50% 1 <= N, C <= 10000;
100% 1 <= N, C <= 100000, 1 <= 商品在每个城市的价格 <= 100000.
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！