分数: 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位整数。