## Description

1 Problem statement

You live in a country with n cities and n−1 bidirectional roads. The transport network of this country can be modelled as a rooted, weighted tree:

• The vertices are labelled 1,2,…,n and each vertex represents a city.

• The edges are labelled 1,2,…,n − 1. Road i connects city i + 1 to its parent p[i]

• Associated with each road i is a weight w[i]. w[i] represents the amount of fuel in liters, required to travel from city i+1 to its parent p[i], or vice versa (the roads are bidirectional, and the fuel required to traverse the road in either direction is w[i] liters).

City i(1 ≤ i ≤ n) contains a petrol station which charges d[i] dollars per liter (different cities can have different prices).

You are currently in your car in city 1 and wish to travel to city n. Your car is currently out of petrol and you wish to find the cheapest way to travel from city 1 to city n (i.e. minimize the total amount of money you pay to all petrol stations). For the purposes of this problem, we will make the following

assumptions:

• There is no limit to the amount of petrol that your car can hold.

• The amount of petrol in your car is not allowed to be negative.

• You are not allowed to sell excess petrol to petrol stations.

• You are allowed to end the journey with an empty petrol tank.

Time complexity requirement: O(n2) for full credit (5 points). Solutions which run in O(n3) will get partial credit (3 points).

2 Input format

The first line of the input consists of a single integer n. The second line of the input consists of n space-separates integers d[1] d[2] … d[n], representing the cost of petrol in city i. n − 1 lines then follow. The i-th of these line contains two space-separated

integers p[i] and w[i].

3 Output format

Output a single integer, the minimum cost required to travel from city 1 to n, followed by a endline character.

4 Constraints

All test cases will satisfy the following constraints:

• 3 ≤ n ≤ 10000

• 1 ≤ d[i] ≤ 106 (for each 1 ≤ i ≤ n)

• 1 ≤ p[i] ≤ i

• 1 ≤ w[i] ≤ 106

The test cases under the partial task will also satisfy n ≤ 500.

5 Sample input and output

5.1 Sample input 1

3

10 1 1

1 1

1 100

5.2 Sample output 1

111

5.3 Sample input 2

5

14 2 2 11 7

1 10

1 1

1 3

1 1

5.4 Sample output 2

14

Submit your solution to CodeCrunch in either C++ or Java. You need to pass all test cases to get 5 points (or all test cases satisfying n ≤ 500 to get 3 points). The tasks will be labelled full and partial.

• If your final submission to full is correct, you will receive 5 points and your submission to partial will be ignored. If you are confident of your submission to full, you do not need to submit to partial.

• If multiple submissions are made, only the last one will be graded.

No proofs are required.

2.

You are not allowed to share code.

## Reviews

There are no reviews yet.