IOI 나라는 N개의 도시와 도시들을 잇는 N − 1개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 도시를 도로만을 사용하여 오갈 수 있다. 즉, IOI 나라의 도로망은 트리 구조를 이룬다.

도시에는 각각 0 이상 N − 1 이하의 서로 다른 번호가 붙어 있으며, 0번 도시가 IOI 나라의 수도이다.

또 모든 0 ≤ i ≤ N − 2에 대해서 i번 도로는 U[i]번 도시와 V [i]번 도시를 연결하며 도로의 길이는 W[i] km 이다.

IOI 나라에서는 도시별로 택시의 운임이 다르다. 구체적으로, 모든 0 ≤ i ≤ N − 1에 대해 i번 도시에서 출발하는 택시는 기본 요금 A[i]원과 거리 당 요금 B[i]원을 가진다.

이는 i번 도시에서 택시를 타고 출발하여 d km 만큼 이동할 경우 A[i] + d × B[i]원을 내야 함을 뜻한다.

서현이는 현재 수도인 0번 도시에 살고 있다. 서현이는 다른 도시들로 택시를 타고 여행을 떠나려고 한다.

서현이가 어떤 도시에 도착했을 때, 서현이는 타던 택시를 계속 타거나 그 도시에서 출발하는 택시로 갈아탈 수 있다.

물론 택시를 갈아타면 기본 요금을 내야 하며 거리 당 요금도 변할 수 있다.

0번 도시에서 출발하여 다른 모든 도시들로 가는 데 필요한 최소 비용을 각각 계산하여라.

제약 조건

• 2 ≤ N ≤ 100 000

• 모든 i에 대해 0 ≤ A[i] ≤ 10^12 (0 ≤ i ≤ N − 1)

• 모든 i에 대해 0 ≤ B[i] ≤ 1 000 000 (0 ≤ i ≤ N − 1)

• 모든 i에 대해 0 ≤ U[i], V [i] ≤ N − 1; U[i] != V [i] (0 ≤ i ≤ N − 2)

• 모든 i에 대해 1 ≤ W[i] ≤ 1 000 000 (0 ≤ i ≤ N − 2)

여러분은 아래 함수를 구현해야 한다.

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

이 함수는 단 한 번만 호출된다.
$A$: 크기가 $N$인 정수 배열. 모든 $i$ ($0 ≤ i ≤ N - 1$)에 대해, $A[i]$는 $i$번 도시에서 출발하는 택시의 기본 요금이다.
$B$: 크기가 $N$인 정수 배열. 모든 $i$ ($0 ≤ i ≤ N - 1$)에 대해, $B[i]$는 $i$번 도시에서 출발하는 택시의 이동 거리(km)당 요금이다.
$U$, $V$, $W$: 크기가 $N - 1$인 정수 배열. 모든 $i$ ($0 ≤ i ≤ N - 2$)에 대해, $U[i]$번 도시와 $V[i]$번 도시를 잇는 길이 $W[i]$ km의 도로가 있다.
이 함수는 크기가 $N - 1$인 배열 $C$를 반환해야 한다. 모든$i$ ($0 ≤ i ≤ N - 2$)에 대해, $C[i]$는 0$0$번 도시에서 출발해 $i + 1$번 도시까지 가는 데 필요한 최소 비용과 같아야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

택시 여행 timer 5s memory 1024MB

택시 여행 5s 1024MB