Taxi Travel

This problem is adapted from the 2023 IOI Korea Selection Contest. In IOI country, there are N cities connected by N-1 bidirectional roads such that any two cities are reachable from one another (i.e. the road network forms a tree). The cities are numbered from 0 to N-1, with city 0 being the capital. For each road i (where 0 \le i \le N-2), it connects city U[i] and city V[i] and has a length of W[i] kilometers.

Each city has its own taxi service with different fee structures. In particular, for each city i (where 0 \le i \le N-1), the taxi departing from city i charges a base fee A[i] and a per kilometer fee B[i]. Thus, if you ride a taxi from city i for a distance of d kilometers, you need to pay:

[ \text{Cost} = A[i] + d \times B[i] ]

Starting at the capital (city 0), you want to travel to every other city with minimum total cost. When you arrive in a city, you can either continue riding the taxi you are currently in or switch to the taxi service of that city (which will incur its own base fee and per kilometer cost). More formally, if the unique simple path from city 0 to city v is given by 0 = p₀, p₁, ..., p_k = v, then you may choose an index j (with 0 \le j < k) at which you switch taxis. The cost incurred for the segment starting at city p_j and ending at city v is:

[ A[p_{j}] + B[p_{j}] \times (d(v) - d(p_{j})) ]

where d(x) is the distance from the capital to city x. Additionally, you need to add the cost incurred to reach city p_j (which is computed similarly). Your task is to compute the minimum cost for traveling from city 0 (the capital) to every other city.

You need to implement the following function:

// C++ signature
vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W);

Note: The submitted code should not include any input/output operations.

inputFormat

The function travel receives the following arguments:

• A: an array of N long long integers, where A[i] is the base taxi fee at city i.
• B: an array of N integers, where B[i] is the per kilometer fee at city i.
• U, V, W: arrays each of size N-1. For each i (with 0 \le i < N-1), there is a bidirectional road connecting city U[i] and city V[i] with a length of W[i] kilometers.

The road network forms a tree rooted at city 0.

outputFormat

The function should return an array of N-1 long long integers C, where C[i] is the minimum cost required to travel from city 0 to city i+1.

sample

A = [10, 20, 30, 40]
B = [1, 2, 3, 4]
U = [0, 0, 1]
V = [1, 2, 3]
W = [5, 3, 2]

15 13 17