P5306 [COCI 2018/2019 #5] Transport

A country has $n$ cities. Each city has a gas station with fuel supply $a_i$. There are $n-1$ roads connecting these cities into a tree structure. For a truck to travel from city $u$ to city $v$, the amount of fuel in the truck must be at least the distance between $u$ and $v$. Each time the truck arrives at a city, it can refuel by an amount not exceeding the fuel supply of that city's gas station. Assume the truck's fuel tank has infinite capacity, and it consumes one unit of fuel for each kilometer traveled. Please calculate how many ordered pairs $(u,v)$ satisfy: A truck whose initial fuel is $0$ can start from city $u$, reach city $v$, and $u \neq v$. Note that the truck can only travel along a simple path, meaning it cannot go back.

The first line contains a positive integer $n$. The second line contains $n$ positive integers $a_i$, representing the fuel supply of each gas station. The next $n-1$ lines each contain three positive integers $u,v,w$, indicating that there is a road of length $w$ between cities $u$ and $v$.

Output one integer in a single line, representing the answer.

### Explanation for Sample 1: The only feasible pair is $(1,2)$, meaning only $1\rightarrow 2$ is feasible. ### Constraints: For $20\%$ of the testdata: $1\le n \le 5000$。 For $40\%$ of the testdata: The tree is a chain. For $100\%$ of the testdata: $1\le n \le 10^5$。 $1\le u,v \le n$。 $1\le w,a_i \le 10^9$。 Translated by ChatGPT 5