Problem 1767. -- [Ceoi2009]harbingers -- 衡阳八中OJ离线版-2014-11-041767: [Ceoi2009]harbingers
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 283 Solved: 80
[Submit][Status]Description
给定一颗树,树中每个结点有一个邮递员,每个邮递员要沿着唯一的路径走向capital(1号结点),每到一个城市他可以有两种选择:
1.继续走到下个城市
2.让这个城市的邮递员替他出发。
每个邮递员出发需要一个准备时间W[I],他们的速度是V[I],表示走一公里需要多少分钟。
现在要你求出每个城市的邮递员到capital的最少时间(不一定是他自己到capital,可以是别人帮他)
N<=100000
3 ≤ N ≤ 100 000
0 ≤ Si≤ 10^9
1 ≤ Vi≤ 10^9
The length of each road will not exceed 10 000
For 20% of the tests, N ≤ 2 500
For 50% of the tests, each town will have at most 2 adjacent roads (i.e., the graph of
roads will be a line)
Input
N
以下N-1行A,B,C三个数表示A,B之间有一条长为C的边。
再N行每行两数Wi,Vi
输出有一行N-1个数表示如题所述。
Output
Sample Input
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
Sample Output
206 321 542 328
HINT
Source
[Submit][Status]
HOME
Back