[Ceoi2009]harbingers

时间限制：10s 空间限制：64MB

题目描述

给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向capital(1号结点)，每到一个城市他可以有两种选择： 1.继续走到下个城市 2.让这个城市的邮递员替他出发。每个邮递员出发需要一个准备时间W[I]，他们的速度是V[I]，表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到capital的最少时间(不一定是他自己到capital，可以是别人帮他） N<=100000 0="" 1="" 2="" 3="" 10="" 100="" 500="" ≤="" n="" 000="" si≤="" 10^9="" vi≤="" the="" length="" of="" each="" road="" will="" not="" exceed="" for="" 20%="" tests,="" 50%="" town="" have="" at="" most="" adjacent="" roads="" (i.e.,="" graph="" be="" a="" line)="" <="" p="">

输入格式

N 以下N-1行A,B,C三个数表示A,B之间有一条长为C的边。再N行每行两数Wi,Vi 输出有一行N-1个数表示如题所述。

输出格式

样例输入

样例输出

206 321 542 328

提示

题目来源

没有写明来源