#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Hua Jun has constructed an underground bunker in his basement to prepare for emergencies. The underground
bunker consists of *N* rooms numbered 1 to *N*, connected by *N* - 1 corridors. Each corridor
connects two different rooms and have a certain length. To prevent himself from getting trapped, Hua Jun
has ensured that each room can be reached from any other room via a unique path by walking down one or more
corridors, without passing through the same corridor twice. The distance Hua Jun has to walk to go from room
*i* to room *j* is denoted by dist(*i*, *j*).

Each room in Hua Jun's underground bunker is equipped with an alarm system, consisting of a siren and a
sound sensor. Each siren can be activated by either manually switching it on, or by triggering the
sound sensor via the siren from the alarm system of another room. The sound sensor in room *i* activates
the alarm in room *i*. The siren in room *i* has power *D _{i}*, and can trigger all the
sound sensors in all rooms

*j*where dist(

*i*,

*j*) ≤

*D*.

_{i}When there is an emergency, Hua Jun wants to activate all the sirens. Turning all of them on manually is too slow and can be dangerous for an emergency. Hence, Hua Jun wonders, what is the minimum number of sirens he must turn on manually such that the sirens in all rooms are activated.

## Input

The first line contains a single integer *N*, the number of rooms.

The second line contains *N* integers, the *i*th integer is the value of *D _{i}*.

The next *N* - 1 lines each describe a corridor.

The *i*th line contains three integers *U _{i}*,

*V*and

_{i}*L*, where the

_{i}*i*th corridor connects rooms

*U*and

_{i}*V*and has a length of

_{i}*L*.

_{i}## Output

Output a single integer, the minimum number of sirens Hua Jun has to turn on manually.

## Limits

For all subtasks, 0 ≤ *D _{i}* ≤ 10

^{9}. 1 ≤

*L*≤ 10

_{i}^{9}.

Subtask 1 (16%): 1 ≤ *N* ≤ 15.

Subtask 2 (23%): 1 ≤ *N* ≤ 100.

Subtask 3 (17%): 1 ≤ *N* ≤ 3000.

Subtask 4 (24%): 1 ≤ *N* ≤ 100 000.

Subtask 5 (20%): 1 ≤ *N* ≤ 300 000.

Subtask 6 (0%): Sample Testcases

## Sample Testcase 1

### Input

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

### Output

3

### Explanation

Hua Jun switches on the sirens in rooms 2, 4, 8. The siren in room 4 activates the siren in room 5, which in turn activates sirens in rooms 6 and 7. The siren in room 2 activates the siren in room 3. The siren in room 8 activates sirens in rooms 1, 9 and 10.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 16 | 27 | 4s | 512MB | Minimum |

2 | 23 | 51 | 4s | 512MB | Minimum |

3 | 17 | 78 | 4s | 512MB | Minimum |

4 | 24 | 104 | 4s | 512MB | Minimum |

5 | 20 | 130 | 4s | 512MB | Minimum |

6 | 0 | 1 | 4s | 512MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o alarm -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512