# KOITST 23 Taxi

https://www.acmicpc.net/problem/27510

IOI Country consists of $N$ cities connected by $N - 1$ bidirectional roads, and any two different cities can be traveled between using only roads. In other words, the road network of IOI Country forms a tree structure.

Each city is numbered from $0$ to $N - 1$, and the city with number $0$ is the capital of IOI Country. Additionally, for all $0 ≤ i ≤ N - 2$, the $i$-th road connects city $U[i]$ and city $V[i]$, with a length of $W[i]$ km.

In IOI Country, taxi fares vary from city to city. Specifically, for all $0 ≤ i ≤ N - 1$, a taxi departing from city $i$ has a base fare of $A[i]$ won and a fare per kilometer of $B[i]$ won. This means that when traveling $d$ km from city $i$ by taxi, one must pay $A[i] + d \times B[i]$ won.

Seohyun currently lives in city $0$, the capital. Seohyun plans to travel to other cities by taxi. When arriving at a city, Seohyun can either continue riding the taxi she took or switch to a taxi departing from that city. Of course, switching taxis incurs a base fare, and the fare per kilometer may change as well.

Compute the minimum cost required to travel from city $0$ to every other city.

## Implementation

You should implement the following function:

`vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W)`

This function will be called exactly once.

Input Parameters:

* A: An array of integers of size $N$. For all $i$ ($0 ≤ i ≤ N - 1$), $A[i]$ represents the base fare of a taxi departing from city $i$.
* B: An array of integers of size $N$. For all $i$ ($0 ≤ i ≤ N - 1$), $B[i]$ represents the fare per kilometer of a taxi departing from city $i$.
* U, V, W: Arrays of integers of size $N - 1$. For all $i$ ($0 ≤ i ≤ N - 2$), there is a road of length $W[i]$ km connecting city $U[i]$ and city $V[i]$.

This function should return an array C of size $N - 1$. For all $i$ ($0 ≤ i ≤ N - 2$), C[i] should be equal to the minimum cost required to travel from city $0$ to city $i + 1$.

## Constraints

$2 ≤ N ≤ 100,000$
For all $i$, $0 ≤ A[i] ≤ 10^{12}$ and $0 ≤ B[i] ≤ 1,000,000$
For all $i$, $0 ≤ U[i], V[i] ≤ N - 1$; $U[i] ≠ V[i]$
For all $i$, $1 ≤ W[i] ≤ 1,000,000$

## Subtasks:

1. $N ≤ 20$ (7 points)
1. For all $i$, $U[i] = i$; $V[i] = i + 1$ ($0 ≤ i ≤ N - 2$) (8 points)
1. $N ≤ 2,000$ (13 points)
1. For all $i$, $B[i] ≤ 30$ ($0 ≤ i ≤ N - 1$) (17 points)
1. There are at most $2,000$ cities where $B[i] ≠ 0$ ($0 ≤ i ≤ N - 1$) (29 points)
1. No additional constraints (26 points)

## Sample grader

The sample grader will receive input in the following format:

Line $1$: $N$
Line $2$: $A[0]$ $A[1]$ $\cdots$ $A[N - 1]$
Line $3$: $B[0]$ $B[1]$ $\cdots$ $B[N - 1]$
Lines $4 + i$ ($0 ≤ i ≤ N - 2$): $U[i]$ $V[i]$ $W[i]$

The sample grader will print:

Line $i$: The $i$-th element of the array returned by travel

# Example

Consider the case where $N = 5$, $A = [10, 5, 13, 4, 3]$, $B = [10, 7, 5, 9, 1]$, $U = [1, 0, 3, 2]$, $V = [0, 2, 2, 4]$, and $W = [1, 5, 10, 3]$.

The sample grader will call the function as follows:

travel([10, 5, 13, 4, 3], [10, 7, 5, 9, 1], [1, 0, 3, 2], [0, 2, 2, 4], [1, 5, 10, 3])

The map of IOI Country is shown below:


* The minimum cost to travel from city $0$ to city $1$ is $20$ won by taking a taxi from city $0$ to city $1$ directly.
* The minimum cost to travel from city $0$ to city $2$ is $60$ won by taking a taxi from city $0$ to city $2$ directly.
* The minimum cost to travel from city $0$ to city $4$ is $88$ won by taking a taxi from city $0$ to city $1$, switching to a taxi from city $1$ to city $2$, and then taking a taxi from city $2$ to city $4$.
* The minimum cost to travel from city $0$ to city $3$ is $104$ won by taking a taxi from city $0$ to city $1$, switching to a taxi from city $1$ to city $2$, then taking a taxi from city $2$ to city $4$, switching to a taxi from city $4$ to city $2$, and finally taking a taxi from city $2$ to city $3$.

The function should return [20, 60, 104, 88].