E - Tree and Hamilton Path 2

Contest Duration: 2024-07-06(Sat) 12:00 - 2024-07-06(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Tree and Hamilton Path 2 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

AtCoder国には $1$ から $N$ の番号がついた $N$ 個の街と $1$ から $N-1$ の番号がついた $N-1$ 本の道路があります。

道路 $i$ は街 $A_i$ と街 $B_i$ を双方向に結び、長さは $C_i$ です。どの街同士も、いくつかの道路を通って互いに行き来することができます。

いずれかの街を出発し、道路による移動で全ての街を $1$ 度以上訪れるための移動距離の最小値を求めてください。

制約

$2 \leq N \leq 2\times 10^5$
$1 \leq A_i,B_i \leq N$
$1 \leq C_i \leq 10^9$
入力は全て整数である
どの街同士も、いくつかの道路を通って互いに行き来できる

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $B_1$   $C_1$ 
 $\vdots$ 
 $A_{N-1}$   $B_{N-1}$   $C_{N-1}$

出力

答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$4 \to 1 \to 2 \to 1 \to 3$ と移動すると移動距離の合計は $11$ となり、これが最小値です。

最初の街に戻ってくる必要はないことに注意してください。

入力例 2Copy

Copy

10
10 9 1000000000
9 8 1000000000
8 7 1000000000
7 6 1000000000
6 5 1000000000
5 4 1000000000
4 3 1000000000
3 2 1000000000
2 1 1000000000

出力例 2Copy

Copy

9000000000

オーバーフローに注意してください。

Score : $500$ points

Problem Statement

In the nation of AtCoder, there are $N$ cities numbered $1$ to $N$ and $N-1$ roads numbered $1$ to $N-1$ .

Road $i$ connects cities $A_i$ and $B_i$ bidirectionally, and its length is $C_i$ . Any pair of cities can be reached from each other by traveling through some roads.

Find the minimum travel distance required to start from a city and visit all cities at least once using the roads.

Constraints

$2 \leq N \leq 2\times 10^5$
$1 \leq A_i, B_i \leq N$
$1 \leq C_i \leq 10^9$
All input values are integers.
Any pair of cities can be reached from each other by traveling through some roads.

Input

The input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $B_1$   $C_1$ 
 $\vdots$ 
 $A_{N-1}$   $B_{N-1}$   $C_{N-1}$

Output

Print the answer.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

If you travel as $4 \to 1 \to 2 \to 1 \to 3$ , the total travel distance is $11$ , which is the minimum.

Note that you do not need to return to the starting city.

Sample Input 2Copy

Copy

10
10 9 1000000000
9 8 1000000000
8 7 1000000000
7 6 1000000000
6 5 1000000000
5 4 1000000000
4 3 1000000000
3 2 1000000000
2 1 1000000000

Sample Output 2Copy

Copy

9000000000

Beware overflow.