AT_abc369_g.[ABC369G] As far as possible

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一棵包含 $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
```
5
1 2 3
2 3 5
2 4 2
1 5 3
```
输出#1
```
16
22
26
26
26
```

输入#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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页