尽可能远

题目描述

给你一棵有 $N$ 个顶点的树。 顶点编号为 $1,2,\ldots,N$。

第 $i$ 条边 ($1\le i\le N-1$) 连接顶点 $U_i$ 和 $V_i$，长度为 $L_i$。

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

高桥和青木玩一个游戏。游戏过程如下。

首先，青木在树上指定 $K$ 个互不相同的顶点。

然后，高桥构造一条从顶点 $1$ 出发、回到顶点 $1$、且经过青木指定的所有顶点的 walk（游走）。

分数定义为高桥构造的 walk 的长度。高桥希望最小化分数，而青木希望最大化分数。 求双方都最优行动时的分数。

Walk 的定义

无向图（可以是树）上的 walk 是一个由 $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}$。序列中同一个顶点或同一条边可以多次出现。 若存在至少一个 $i$ ($1\le i\le k$) 使得 $v_i=x$，则称 walk 经过顶点 $x$。（这样的 $i$ 可能有多个。） walk 分别从 $v_1$ 出发、在 $v_k$ 结束，walk 的长度是 $e_1,e_2,\ldots,e_{k-1}$ 的长度之和。

输入格式

输入按以下格式从标准输入给出：

$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\le i\le N)$ 输出 $K=i$ 时的答案。

样例

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

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\ge 3$，双方最优行动时的分数为 $26$。

3
1 2 1000000000
2 3 1000000000

4000000000
4000000000
4000000000

注意答案可能超出 $32$-bit 整数的范围。

数据范围

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