← 返回题目列表

AtCoder · tkppc2015_e

E. 看不见的边界

中文机器翻译题面 查看原题

本题的输入示例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