Non-redundant Drive

Time limit2sMemory limit512 MB

Summary

In a tree where each node gives g fuel and each edge costs d, find the longest simple path from any start such that the running fuel never drops below zero, refueling once per node.

Level: Hard8 of 10
Topics: Tree, DFS, Dynamic programming, Greedy
Solved: No attempts yet

Problem

The people of the JAG kingdom hate redundancy. For example, the $N$ cities of the kingdom are connected by exactly $N-1$ bidirectional roads, and every city is reachable from every other city by some roads. Under this condition, the number of paths between any two cities is exactly one. This is a non-redundant road network.

One day you, a citizen of the JAG kingdom, decide to travel through as many cities of the kingdom as possible by car. The car has an infinitely large tank, but the tank is empty at first. The car consumes 1 liter of gasoline per 1 km.

Each city has exactly one gas station, and the gas station of city $x$ supplies $g_x$ liters of gasoline to your car. You may choose not to visit some gas stations during the travel. But you never refuel twice or more at the same gas station, because that is redundant. Each road of the kingdom has a distance between its two cities, and the distance of the $i$ -th road is $d_i$ km. You never pass through the same city or the same road twice or more either, because that is redundant.

If the amount of stored gasoline becomes zero, the car cannot move, and the travel ends there. The initially empty tank is not a problem: you can start at the gas station of any city in the kingdom. Also, each road directly connects the gas stations at its two ends (the spirit of non-redundancy avoids redundant moves inside a city), so you can refuel at a city even if the tank becomes empty exactly when you arrive there.

Write a program that computes the maximum number of cities you can travel through under this non-redundancy policy.

Input

The input consists of a single test case.

N
g1 ... gN
a1 b1 d1
...
aN-1 bN-1 dN-1

The first line contains an integer $N$ ( $1 \le N \le 100000$ ), the number of cities in the kingdom. The second line contains $N$ integers; the $i$ -th of them is $g_i$ ( $1 \le g_i \le 10000$ ), the amount of gasoline the gas station of city $i$ supplies. The following $N-1$ lines describe the roads: the $j$ -th of them contains $a_j$ , $b_j$ , and $d_j$ , meaning that the $j$ -th road bidirectionally connects city $a_j$ and city $b_j$ ( $1 \le a_j, b_j \le N$ , $a_j \ne b_j$ ) with distance $d_j$ ( $1 \le d_j \le 10000$ ). All cities of the kingdom are connected by the roads.

Output

Print the maximum number of cities you can travel through, starting from any city, under the constraint that you refuel at most once per gas station.

Examples3

Example 1
Input
```
5
5 8 1 3 5
1 2 4
2 3 3
2 4 3
1 5 7
```
Expected output
```
4
```
Example 2
Input
```
2
10 1
1 2 10
```
Expected output
```
2
```
Example 3
Input
```
5
1 3 5 1 1
1 2 5
2 3 3
2 4 3
1 5 5
```
Expected output
```
3
```