P3994 Highway

Country C has a well-connected highway network that forms a tree. There are $n$ cities in Country C, connected by a total of $n - 1$ highways. Except for the capital, city $1$, each city has a local passenger transport company that can dispatch vehicles to various places nationwide. You can regard the network as a tree rooted at $1$. The distance between two cities is defined as the length of the simple path between them. Suppose a person departs from city $i$ to city $j$, which is at distance $D$ from $i$. Then the cost is $P_i \times D + Q_i$ yuan, and it is required that $j$ is an ancestor of $i$. Because national supervision becomes looser farther from the capital, the $P_i$ of transport companies increases with distance from the capital: if city $i$ is an ancestor of city $j$, then $P_i \leq P_j$. Xiao T has become an investigator at the national statistics bureau. He needs to survey the current highway network to find out the cost to reach the capital, city $1$, from every other city. Because reaching the capital may involve multiple transfers (or none), computing this by hand is very complicated. Xiao T is very lazy, so please write a program to solve it.

The first line contains an integer $n$, the number of cities. Lines $2$ through $n$ each describe one city other than the capital. Specifically, line $i$ contains four integers $F_i, S_i, P_i, Q_i$, representing the parent city of city $i$, the length of the highway from city $i$ to its parent, and the two fare parameters of city $i$.

Output $n - 1$ lines, each containing an integer. The $i$-th line contains the minimum cost to reach the capital starting from city $i + 1$.

Constraints and Notes: - For the first $40\%$ of the testdata, $n \leq 1000$. - For another $20\%$ of the testdata, $F_i = i - 1$. - For all the testdata, $1 \leq n \leq 10^6$, $0 \leq P_i, Q_i < 2^{31}$, and the result is guaranteed not to exceed $2^{63} - 1$. Translated by ChatGPT 5