本题的输入示例1是错误的,但已被修正。
另外,输入示例2与法官系统中使用的不同,所以我做了修改。 不过,之前的测试用例也满足了这些问题的要求。
重新评判也已完成。
問題文
离开地牢后,我发现自己身处一所学校。
因为那所学校的社团活动似乎很活跃,乔伊西诺先生决定去拜访社团。
他加入的第一个社团里,地板上画了一个魔法阵。
当被问及他做什么时,他说他在研究其他世界。
根据他们的故事,包括这个世界,N存在于世界上,他们N-1这意味着它们通过类似“隐形边界”的门连接着。
此外,世界之间好像是通过穿过一些不可见的边界线来互相往来的。
而且,不可见的边界线i(1 ≦ i ≦ N-1)连接着世界A_i(1 ≦ A_i ≦ N)和
按字典顺序比较B_i(1 ≦ B_i ≦ N),但是在穿过时C_i(1 ≦ C_i ≦ 10^9)会受到伤害。
因此,她们似乎在各自的世界中寻找,总共不受伤害最多也必须经过才能到达的世界。
然而,世界太多了,所以她们调查起来显得非常困难。
于是joisino姐姐决定为她们写一个解决这个问题的程序。
入力
输入是按以下格式从标准输入给出的。
N
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{N-1} B_{N-1} C_{N-1}
- 1行中写着世界的数量N(1 ≦ N ≦ 10^5)。 表示
- 2从线N-1行i在线i写入第th路径的信息, 写入第A_i和 按字典顺序比较B_i和 按字典顺序比较C_i用空格分隔。
配点
本题没有部分分。 答对可得80分。
出力
输出是
由N行组成。
i在线i输出从第几号世界出发到达时需要承受的最多伤害的世界编号。
此外,如果这种世界有多个,请输出其中编号最小的那个。
还在输出末尾包含换行符。
入力例1
3 1 2 10 2 3 15
出力例1
3 3 1
在这种情况下,如下图所示,世界是连通的,世界1从出发到世界3时25总伤害最多,到达世界2从出发到世界3时15总伤害最多,到达世界3从出发到世界1去世界25时总伤害最多。
入力例2
5 1 2 15 1 3 15 1 4 5 4 5 10
出力例2
2 3 2 2 2
在这种情况下,如下图所示,世界是连通的,世界1从出发到世界2到世界2从出发到世界3到世界3从出发到世界2到世界4从出发到世界2到世界5从出发到世界2去时受到的伤害最多。
入力例3
10 8 3 55 9 1 160 1 4 265 9 5 571 2 9 771 4 7 818 9 10 11 2 8 569 4 6 340
出力例3
3 7 7 3 3 3 3 7 3 3