/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 であるような歩道であって、青木君が指定した頂点をすべて通るようなものを構成します。
高橋君が構成した歩道の長さをスコアと定義します。高橋君はスコアをなるべく小さく、青木君はスコアをなるべく大きくしたいです。 2 人が最善に行動したときのスコアを求めてください。
歩道とは
無向グラフ（木を含む）上の歩道とは、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 を通るとは、v_i=x となるような 1\leq i\leq k が 1 つ以上存在することをいう。（複数個存在しても良い。） また、歩道の始点、終点はそれぞれ 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
答えが 32bit 整数型に収まらない可能性があることに注意してください。
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.