← 返回题目列表

AtCoder · abc369_g

G. 尽可能

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

分数: 600 点

问题陈述

你有一棵树 N 顶点。 顶点已编号 1, 2, \ldots, N.
的 i第边缘 (1\leq i\leq N-1) 连接顶点 U_i 和 V_i,长度为 L_i.

对于每个 K=1,2,\ldots, N,解决以下问题。

高桥和青木玩游戏。游戏进行如下。

  • 首先,青木指出 K 树上的不同顶点。
  • 然后,Takahashi 构造一条在顶点开始和结束的步行 1,并穿过 Aoki 指定的所有顶点。

分数定义为 Takahashi 构建的步行长度。高桥想要最小化分数,而青木想要最大化分数。 求双方都发挥最佳状态时的得分。

步行的定义 在无向图(可能是树)上行走是一系列 k 顶点和 k-1 边缘 v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k (其中 k 是正整数) 这样的边缘 e_i 连接顶点 v_i 和 v_{i+1}。相同的顶点或边可以在序列中出现多次。 据说步行穿过顶点 x 如果存在至少一个 i (1\leq i\leq k)这样 v_i=x。 (可以有多个这样的 i。) 据说步行的开始和结束时间为 v_1 和 v_k,步行的长度分别是 e_1, e_2, \ldots, e_{k-1}.

约束

  • 2\leq N\leq 2\times 10^5
  • 1\leq U_i<V_i\leq N
  • 1\leq L_i\leq 10^9
  • 所有输入值均为整数。
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

N
U_1 V_1 L_1
U_2 V_2 L_2
\vdots
U_{N-1} V_{N-1} L_{N-1}

输出

打印 N 行。 的 i第行 (1\leq i\leq N) 应包含问题的答案 K=i.


示例输入 1

5
1 2 3
2 3 5
2 4 2
1 5 3

示例输出 1

16
22
26
26
26

对于 K=1,青木的最佳移动是指定顶点 3,高桥的最优动作是构造一个路径顶点 1 \to 顶点 2 \to 顶点 3 \to 顶点 2 \to 顶点 1,得分为 16.

对于 K=2,青木的最佳着法是指定顶点 3 和 5,而高桥的最佳动作是构建一条路径,例如顶点 1 \to 顶点 5 \to 顶点 1 \to 顶点 2 \to 顶点 3 \to 顶点 2 \to 顶点 1,得分为 22.

对于 K\geq 3,双方都发挥最佳状态时的得分为 26.


示例输入 2

3
1 2 1000000000
2 3 1000000000

示例输出 2

4000000000
4000000000
4000000000

请注意,答案可能不适合 32位整数。