| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 7 초 | 2048 MB | 13 | 5 | 5 | 41.667% |
There are $n$ cities that are connected by $n-1$ roads, forming a tree. Note that each road has a given length.
When you are at city $v,ドル you can take a taxi of the local taxi company to any other city $w$. For this, you have to pay $a_v + d \cdot b_v$ cookies, where $d$ is the distance from $v$ to $w$. In other words, you have to pay the base cost $a_v$ and additionally $b_v$ for each unit of distance traveled.
You are currently at city 1ドル,ドル and for each other city $v,ドル you want to know the minimum cost to get there.
The first line contains one integer $n$ (2ドル \leq n \leq 10^5$) --- the number of cities.
The second line contains $n$ integers $a_i$ (0ドル \leq a_i \leq 10^{12}$) --- the base costs of the taxis.
The third line contains $n$ integers $b_i$ (1ドル \leq b_i \leq 10^6$) --- the cost per distance.
Then $n-1$ lines follow, describing the roads between the cities. Every line contains three integers $u, v,$ and $\ell$ (1ドル \leq u, v \leq n,ドル $u \neq v,ドル 1ドル \leq \ell \leq 10^6$) describing a bidirectional road between cities $u$ and $v$ of length $\ell$.
Output a single line containing $n-1$ integers. The $i$-th of them should be the minimum cost to get to city $i+1$.
3 0 1 2 8 4 4 1 2 1 1 3 7
8 41
2 353 313 928248 475634 2 1 898027
833591767049
Consider the cost to get to city 3ドル$ in the first sample: Driving directly from 1ドル$ to 3ドル$ would cost 0ドル + 7 \cdot 8 = 56$. It is better to drive from 1ドル$ to 2ドル$ with a cost of 8ドル$ and take a second taxi from 2ドル$ to 3ドル$ with a cost of 1ドル + 8 \cdot 4 = 33$. While the distance traveled is larger, the cost is still smaller.