{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e pre { text-align:left; font-family: \"Courier New\", Courier, monospace; font-size: 16px; white-space: pre; line-height:20px; text-indent: 0px; }\u003c/style\u003e\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003e某一天,YellowStar在人生的道路上迷失了方向,迷迷糊糊之中,它误入了一座迷宫中,幸运的是它在路口处发现了一张迷宫的地图。\u003c/p\u003e\n \u003cp\u003e经过它的观察,它发现这个迷宫一共有n个房间,并且这n个房间呈现一个有根树结构,它现在所在的1号房间为根,其它每个房间都有一个上级房间,连接第i个房间和它的上级房间Pi的道路长度为Wi。\u003c/p\u003e\n \u003cp\u003e在地图的背面,记载了这个迷宫中,每个房间拥有一个时空传送门,第i个房间的传送门可以花费Di单位的时间传送到它的任意一个下级房间中(如果x是y的下级房间,并且y是z的下级房间,那么x也是z的下级房间)。\u003c/p\u003e\n \u003cp\u003eYellowStar的步行速度为1单位时间走1长度,它现在想知道从1号房间出发,到每一个房间的最少时间。\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cp\u003e包含多组测试数据。\u003c/p\u003e\n \u003cp\u003e第一行输入n表示n个房间。\u003c/p\u003e\n \u003cp\u003e第二行输出n个数字,第i个数字Di表示i号房间传送器需要花费的时间。\u003c/p\u003e\n \u003cp\u003e接下来n-1行,第i行包含两个数字Pi和Wi,表示i+1号房间的上级房间为Pi,道路长度为Wi。\u003c/p\u003e\n \u003cp\u003e1≤n≤100000\u003c/p\u003e\n \u003cp\u003e1≤Di, Wi≤10^9\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003e输出n个数,第i个数表示从1号房间出发到i号房间的最少时间。 (注意,输出最后一个数字后面也要加一个空格)\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e5\r\n99 97 50 123 550\r\n1 999\r\n1 10\r\n3 100\r\n3 44\r\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e0 99 10 60 54\r\n\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\n \u003cp\u003e初始在1号房间,到1号房间的代价为0。\u003c/p\u003e\n \u003cp\u003e通过1号房间的传送门传送到2号房间,到2号房间的代价为99。\u003c/p\u003e\n \u003cp\u003e通过1号房间走到3号房间,到3号房间的代价为10。\u003c/p\u003e\n \u003cp\u003e通过1号房间走到3号房间,在通过3号房间的传送门传送到4号房间,到4号房间的代价为60。\u003c/p\u003e\n \u003cp\u003e通过1号房间走到3号房间,在通过3号房间走到5号房间,到5号房间的代价为54。\u003c/p\u003e \n "}}]}