#ZF1093. 汽车人变形
汽车人变形
Description
车车喜欢创人,一天车车创完 个城市的人后,来到了一个全是 homo 的新城市,这个城市有 个区域,由 条道路连接,各区域之间都可以互相到达,你可以将整个城市看成一棵树。
第 个区域有 个 homo,连接两个区域的道路上也会有 个 homo。
车车将会选择一个区域空降,并选择一条路径创到底,车车不会回头,现在请你找出一条路径使得车车创到的 homo 总人数最多。
Format
Input
第一行一个正整数 。
第二行 个整数 $a_1,a_2, \cdots, a_n(0 \leqslant a_i \leqslant 10^9)$,表示区域 上的 homo 数量。
接下来 行,每一行包含三个整数 $a,b,w(1 \leqslant a,b \leqslant n, 0 \leqslant w \leqslant 10^9)$,表示 两区域之间有一条 homo 人数为 的道路连接。
Output
输出一个整数,表示车车能创到的最多 homo 数量。
Samples
6
1 1 4 5 1 4
1 3 0
1 2 0
4 5 0
3 4 0
6 3 1
15
Limitation
2s, 1024KiB for each test case.