Transport
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 130\) points
The traffic network in one country consists of \(N\) cities (marked by numbers from 1 to \(N\) ) and \(N-1\)
roads connecting them in a way that all cities are connected. For each road, its length in kilometers is
known, and in each city there is a gas station with a certain amount of fuel.
Due to the fuel shortages that hit the country a few years ago, the leading transport agency has
decided to conduct a survey on the ability to transport goods between cities. Trucks transporting
goods consume one unit of fuel per kilometer and the journey between two neighboring cities is
considered possible if the amount of fuel in a truck's fuel tank at the time of leaving the city is greater
than or equal to the distance between the cities. Each time when a truck is in a city, the truck’s fuel
tank can be filled up by an amount not greater than the amount of fuel in that city’s gas station. The
final assessment of the survey is defined as the number of ordered pairs of cities ( A, B ) such that it is
possible to travel from city \(A\) to city \(B\) under the assumption that a truck starts the journey with an
empty fuel tank (at the beginning of the journey the fuel tank should be filled at the gas station in city
A).
For the simplicity of the research, the following assumptions have been taken into account:
●
A truck’s fuel tank has unlimited capacity.
●
A truck leaving from the city \(A\) travels directly to the city \(B\) , i.e. it does not visit any city on its
journey more than once.
In the test samples totally worth 20% of the points it will hold \(N\) ≤ 5000.
In the test samples totally worth 40% points the network of cities will form a chain, i.e. each city \(x\) (1 ≤
\(x\) < \(N\) ) will be connected to city \(x\) + 1.
1 \(s / 64\) \(MB / 130\) points
The first line contains the integer number N (\(1 \le N \le 100\,000\)), the number of cities.
In the second line there are \(N\) integer numbers \(A\) {i} (\(1 \le A\) ≤10 {9}{ }), the amount of fuel at the gas station
in the \(i\) {th}{ } city.
In the following \(N-1\) rows there are three integer numbers \(U\) , \(V\) (1 ≤ \(U\) , \(V\) ≤ \(N\) , \(U\) ≠ \(V\) ) and \(W\) (1 ≤ \(W\) ≤
10 {9}{ }) describing the road between cities \(U\) and \(V\) of length \(W\) kilometers.
Print the final assessment of the survey.
2
3 1
1 2 2
5
3 1 2 4 5
1 2 3
3 2 2
4 2 6
5 4 3
8
5 2 4 7 8 3 3 6
6 5 5
1 4 5
3 1 2
8 6 5
1 2 3
4 5 3
4 7 5output
output
1
5
29Explanation of the first example:
The only possible way to travel is from city 1 to city 2. The journey from city 2 to city 1 is not possible because
before departure from city 2 a truck cannot have more than 1 unit of fuel in the fuel tank.
Explanation of the second example:
Pairs of cities among which the journey is possible (1, 2), (3, 2), (4, 5), (5, 1) and (5, 4).
평가 및 의견
Transport
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Transport