← 返回题目列表

Codeforces · 1083/A

A. 公平坚果和最佳路径

中文机器翻译题面 查看原题

公平坚果要去树国旅行,那里有$$$n$$$城市。这个国家的大部分土地被森林覆盖。此外,当地的道路系统形成一棵树(无环的连通图)。 Nut 想在 $$$u$$$ 城市租一辆车,并通过一条简单的路径前往 $$$v$$$ 城市。他还没有确定道路,所以是时候去做了。请注意,所选路径只能包含一个顶点。

每个城市都有加油站。由于奇怪的法律,Nut 在第 $$$i$$$ 个城市只能购买 $$$w_i$$$ 升汽油。我们可以假设,他有无限的钱。每条路都有长度,当坚果驶过这条路时,汽油量就会随着长度的增加而减少。当然,努特不能选择一条道路,因为道路是由道路组成的,他在那里耗尽了汽油。他可以在每个访问过的城市购买汽油,即使是第一个和最后一个。

他还想找到路径尽头可以拥有的最大汽油量。帮助他:数一数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 城市数量。

第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \leq w_{i} \leq 10^9$$$) — Nut 在城市中可以购买的最大汽油量。

接下来的 $$$n - 1$$$ 行描述道路并包含三个整数 $$$u$$$、$$$v$$$、$$$c$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq c \leq 10^9$$$, $$$u \ne v$$$),其中 $$$u$$$ 和$$$v$$$ — 由这条道路连接的城市,$$$c$$$ — 其长度。

保证道路连通图是一棵树。

输出

打印一个数字——他在路径尽头可以拥有的最大汽油量。

示例

输入 #1

3
1 3 3
1 2 2
1 3 2

输出 #1

3

输入 #2

5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1

输出 #2

7

注意

第一个示例中的最佳方式是 $$$2 \to 1 \to 3$$$。

第二个示例中的最佳方式是 $$$2 \to 4$$$。