AT_abc369_g [ABC369G] As far as possible

题目描述

给定一棵包含 $N$ 个顶点的树。顶点编号为 $1, 2, \ldots, N$。
第 $i$ 条边（$1\leq i\leq N-1$）连接顶点 $U_i$ 和顶点 $V_i$，长度为 $L_i$。

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

高桥君和青木君进行一个游戏。游戏规则如下：

• 首先，青木君在树上指定 $K$ 个互不相同的顶点。
• 然后，高桥君需要构造一条起点和终点均为顶点 $1$ 的“步道”，并且该步道必须经过青木君指定的所有顶点。

高桥君构造的步道的长度定义为分数。高桥君希望分数尽可能小，青木君希望分数尽可能大。请你求出当两人都采取最优策略时的分数。

步道的定义：在无向图（包括树）上，步道是指由 $k$ 个顶点（$k$ 为正整数）和 $k-1$ 条边交替组成的序列 $v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k$，其中每条边 $e_i$ 连接顶点 $v_i$ 和 $v_{i+1}$。序列中同一个顶点或同一条边可以出现多次。步道经过顶点 $x$，是指存在 $1\leq i\leq k$ 使得 $v_i=x$（可以有多个这样的 $i$）。步道的起点和终点分别为 $v_1$ 和 $v_k$，步道的长度为 $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\leq i\leq N$）输出 $K=i$ 时问题的答案。

输入输出样例 #1

输入 #1

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

输出 #1

16
22
26
26
26

输入输出样例 #2

输入 #2

3
1 2 1000000000
2 3 1000000000

输出 #2

4000000000
4000000000
4000000000

说明/提示

数据范围

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

样例解释 1

当 $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

注意答案可能超出 $32$ 位整数范围。

由 ChatGPT 4.1 翻译