P10602 [CEOI 2009] Harbingers

Given a tree, each node has a postman. Each postman must move along the unique path to the capital (node $1$). Whenever he reaches a city, he has two choices: 1. Continue to the next city. 2. Let the postman of this city depart in his place. Each postman needs a preparation time $W_i$ before departing, and has speed $V_i$, meaning how many minutes it takes to walk $1$ kilometer. Now you need to find, for each city, the minimum time for that city’s postman to reach the capital (not necessarily by himself reaching the capital; someone else may reach it for him).

The first line contains a positive integer $N$. The next $N - 1$ lines each contain three positive integers $A, B, C$, indicating that there is an edge of length $C$ between nodes $A$ and $B$. The next $N - 1$ lines each contain two integers $W_i, V_i$.

Output the minimum time for the postman of each city to reach the capital.

For $20\%$ of the testdata, $N \leq 2500$. For $50\%$ of the testdata, the tree is a chain. For all testdata, $3 \leq N \leq 10^5$, $0 \leq W_i, V_i \leq 10^9$, and each edge length does not exceed $10^4$. Translated by ChatGPT 5