{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"给出N个点,和每个点物品的售价,现在有一个商人,要从u点到v点,他想在路上多赚点钱。他可以从一个城市买物品,然后再卖到另一个城市,但买卖只允许一次,且不能回头走 \n问最多能赚多少"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cdiv\u003e\n \u003cp\u003eThe first line contains \u003ci\u003eN\u003c/i\u003e, the number of cities.\u003cbr\u003eEach of the next \u003ci\u003eN\u003c/i\u003e lines contains \u003ci\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e the goods\u0027 price in each city.\u003cbr\u003eEach of the next \u003ci\u003eN-1\u003c/i\u003e lines contains labels of two cities, describing a road between the two cities.\u003cbr\u003eThe next line contains \u003ci\u003eQ\u003c/i\u003e, the number of paths.\u003cbr\u003eEach of the next \u003ci\u003eQ\u003c/i\u003e lines contains labels of two cities, describing a path. The cities are numbered from 1 to \u003ci\u003eN\u003c/i\u003e. \u003c/p\u003e\n \u003cp\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e, \u003ci\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eQ\u003c/i\u003e ≤ 50000 \u003cbr\u003e\u003c/p\u003e\n \u003c/div\u003e\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cdiv\u003e\n \u003cp\u003eThe output contains \u003ci\u003eQ\u003c/i\u003e lines, each contains the maximum profit of the corresponding path. If no positive profit can be earned, output 0 instead. \u003c/p\u003e\n \u003c/div\u003e\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4\n1 \n5 \n3 \n2\n1 3\n3 2\n3 4\n9\n1 2\n1 3\n1 4\n2 3\n2 1\n2 4\n3 1\n3 2\n3 4\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4\n2\n2\n0\n0\n0\n0\n2\n0\n\u003c/pre\u003e"}}]}