103696: [Atcoder]ABC369 G - As far as possible
Description
Score : $600$ points
Problem Statement
You are given a tree with $N$ vertices.
The vertices are numbered $1$, $2$, $\ldots$, $N$.
The $i$-th edge ($1\leq i\leq N-1$) connects vertices $U_i$ and $V_i$, with a length of $L_i$.
For each $K=1,2,\ldots, N$, solve the following problem.
Takahashi and Aoki play a game. The game proceeds as follows.
- First, Aoki specifies $K$ distinct vertices on the tree.
- Then, Takahashi constructs a walk that starts and ends at vertex $1$, and passes through all the vertices specified by Aoki.
The score is defined as the length of the walk constructed by Takahashi. Takahashi wants to minimize the score, while Aoki wants to maximize it. Find the score when both players play optimally.
Definition of a walk
A walk on an undirected graph (possibly a tree) is a sequence of $k$ vertices and $k-1$ edges $v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k$ (where $k$ is a positive integer) such that edge $e_i$ connects vertices $v_i$ and $v_{i+1}$. The same vertex or edge can appear multiple times in the sequence. A walk is said to pass through vertex $x$ if there exists at least one $i$ ($1\leq i\leq k$) such that $v_i=x$. (There can be multiple such $i$.) The walk is said to start and end at $v_1$ and $v_k$, respectively, and the length of the walk is the sum of the lengths of $e_1$, $e_2$, $\ldots$, $e_{k-1}$.Constraints
- $2\leq N\leq 2\times 10^5$
- $1\leq U_i<V_i\leq N$
- $1\leq L_i\leq 10^9$
- All input values are integers.
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
$N$
$U_1$ $V_1$ $L_1$
$U_2$ $V_2$ $L_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$ $L_{N-1}$
Output
Print $N$ lines. The $i$-th line $(1\leq i\leq N)$ should contain the answer to the problem for $K=i$.
Sample Input 1
5 1 2 3 2 3 5 2 4 2 1 5 3
Sample Output 1
16 22 26 26 26
For $K=1$, Aoki's optimal move is to specify vertex $3$, and Takahashi's optimal move is to construct a path vertex $1$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $2$ $\to$ vertex $1$, resulting in a score of $16$.
For $K=2$, Aoki's optimal move is to specify vertices $3$ and $5$, and Takahashi's optimal move is to construct a path such as vertex $1$ $\to$ vertex $5$ $\to$ vertex $1$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $2$ $\to$ vertex $1$, resulting in a score of $22$.
For $K\geq 3$, the score when both players play optimally is $26$.
Sample Input 2
3 1 2 1000000000 2 3 1000000000
Sample Output 2
4000000000 4000000000 4000000000
Beware that the answer may not fit in a $32$-bit integer.
Output
得分：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$个不同的顶点。
- 然后，高桥构建一个从顶点$1$开始和结束的路径，并经过青木指定的所有顶点。
得分定义为高桥构建的路径长度。高桥想最小化得分，而青木想最大化得分。
找出当双方都采取最优策略时的得分。
路径的定义
在无向图（可能是树）上的路径是由$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\leq i\leq k$）使得$v_i=x$，则称路径经过顶点$x$。
路径被认为是始于$v_1$并终于$v_k$，路径的长度是$e_1$，$e_2$，$\ldots$，$e_{k-1}$的长度的总和。
约束条件
- $2\leq N\leq 2\times 10^5$
- $1\leq U_i
- $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$。