最佳加油路径 - 代码源竞赛平台

题目描述

蜗蜗准备开车旅行。地图上有 $n$ 个城市，编号为 $1$ 到 $n$ ，城市之间的道路构成一棵树。第 $i$ 个城市有一个加油站，蜗蜗经过这个城市时最多可以补充 $w_i$ 升汽油。通过一条长度为 $c$ 的道路需要消耗 $c$ 升汽油。

蜗蜗可以任选起点和终点，并沿着它们之间的简单路径行驶，也可以只停留在一个城市。起点加油前的油量为 $0$ ，起点和终点都可以加油。行驶过程中，油量不能变成负数。

请你求出蜗蜗到达终点并加油后，最多能够剩下多少升汽油。

第一行包含一个整数 $n$ ，表示城市的数量。

第二行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$ ，表示每个城市最多可以补充的汽油量。

接下来 $n-1$ 行，每行包含三个整数 $u,v,c$ ，表示城市 $u$ 和城市 $v$ 之间有一条长度为 $c$ 的无向道路。

输出一行一个整数，表示到达终点并加油后最多能够剩下的汽油量。

蜗蜗可以按照城市 $1,2,3$ 的顺序行驶。

在城市 $1$ 加油后有 $4$ 升汽油；到达城市 $2$ 并加油后有 $4-2+1=3$ 升；到达城市 $3$ 并加油后有 $3-3+5=5$ 升。

直接选择城市 $3$ 作为起点和终点，也可以剩下 $5$ 升汽油。

对于 100% 的数据，保证 $1\le n\le 3\times 10^5$ ， $0\le w_i\le 10^9$ ， $1\le u,v\le n$ ， $1\le c\le 10^9$ 。

输入的道路构成一棵树。