408805: GYM103328 B Apple Tree

There is a huge apple tree in your backyard. After years of growth, the tree is now full of apples. You know that the tree consists of $$$N$$$ nodes, and there are $$$a_i$$$ apples on the $$$i$$$-th node. You also know the length of each edge in the tree. You are planning to harvest the apples on the tree. To do that, you come up with a unique way of harvesting apples. Firstly, you select a set of nodes from which you are going to collect apples. Then you design a route that passes through all the nodes you selected and returns to the starting node (the route can start from any node in the tree). The score of a harvesting plan is defined as the total amount of harvested apples subtracting the total length of the route. Find the highest score among all harvesting plans.

The first line consists of a single integer $$$N$$$, representing the number of nodes.

The second line consists of $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$, representing the number of apples on the nodes.

The following $$$N-1$$$ lines describe the tree. Each line consists of three integers, $$$u_i, v_i, l_i$$$, meaning that there is an edge of length $$$l_i$$$, connecting the $$$u_i$$$-th node and the $$$v_i$$$-th node.

• $$$1 \leq N \leq 10^{6}$$$
• $$$1 \leq u_i, v_i \leq N$$$
• $$$1 \leq a_i, l_i \leq 10^{9}$$$
• It is guaranteed that the input forms a tree

Output one line containing an integer, representing the highest possible score.

4
3 3 3 3
1 2 3
2 3 1
2 4 2

4

4
3 3 3 3
1 2 10
2 3 10
2 4 10

3

10
5 5 7 10 9 5 10 9 10 7
6 3 10
1 4 2
9 1 6
8 5 10
2 6 9
8 2 6
8 7 4
9 8 1
9 10 8

19