Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!