PID673 / 决斗:纯洁之光
题目描述

一天大家都在机房里纯洁着,HSW突然仰天长啸,大笑三声,说道:“Wsing之光完成了,我就要成为Wsing光明之神了嘿嘿!”。

“Wsing?Wsing!难道HSW是Wsing党的间谍?” ALEJ又仔细一想,恍然大悟,纯洁党的对头——Wsing党的领袖就叫做猥琐皇(WSH),那不就是HSW么!

ALEJ刚想指挥纯洁党按秩序撤退,说时迟,那时快,HSW竟开始朝不同的方向发射Wsing之光,吓得连钛合金眼都没有的ALEJ等人四处逃窜。大家很快就跑散了,HSW说,这不行,都给我回来,我还没打够呢,所有机器,开始发射Wsing之光。顿时,机房每一台好用的机器都开始按照WSH的指令发射Wsing之光。

机房共有N-1台机器,分别被标号为2,3,……,N,WSH会时不时命令一些机器发射Wsing之光。第i台机器发射的Wsing之光有一个固定的速度Vi s/m,需要一个发射准备时间Si s。所有机器发射的Wsing之光都必须回归到WSH那去。有些机器距离WSH过远,他的Wsing之光没有WSH的神力,飞不了那么远,更不能追着ALEJ到处跑,只能先飞到一个指定的机器,然后继续飞行。(每一个机器都有且只有一个指定的机器可以到达,只能是其他机器中的某一个,也可以是WSH,数据保证所有Wsing之光最后一定都会到达WSH,否则就不能把跑散的人都赶回来),当一个Wsing之光以Va s/m到达机器b时,它可以瞬间补充能量,并以Va s/m的速度继续飞向机器b所指定的机器;或者它会转化成激发能来激发机器b发射Wsing之光,机器b会先准备发射,然后以Vb s/m的速度飞向机器b所指定的机器。

ALEJ等人也在加紧研究究极武器:纯洁之光,来对抗Wsing之光。ALEJ想知道每个机器发射的Wsing之光从发射到到达WSH所需要的最短时间,可他实在太忙了,你能帮他么= =。

【数据规模】

3<=N<=100,000

0<=Si<=10^9

1<=Vi<=10^9

0<=d<=1,000

对于20%的数据,N<=2500

对于50%的数据,每一台机器只会接收到一个Wsing之光。

输入格式

输入第一行包括一个正整数N,接下来的N-1行中,每一行包括三个整数u v d,表示第u台机器到第v台机器之间联通,且距离为d m(第1台机器代表WSH,且两台机器会中会有一台机器指向另一台机器,WSH不指向任何一台机器),接下来会有N-1对整数Si Vi,第i对整数描述第i+1台机器:Si是该机器发射前的准备时间,Vi是该机器发射的Wsing之光的速度。

输出格式

输出仅包括n-1个整数,第i个整数代表从第i+1个机器发射Wsing之光到WSH所需要的最短时间。每两个相邻整数之间用一个空格分开。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论