Tree and Hamilton Path 2

题目描述

在 AtCoder 国，有 $N$ 个编号为 $1$ 到 $N$ 的城市和 $N-1$ 条编号为 $1$ 到 $N-1$ 的道路。 道路 $i$ 双向连接城市 $A_i$ 与 $B_i$，其长度为 $C_i$。任意一对城市之间都可以通过若干道路互相到达。 求从某个城市出发，经过道路访问所有城市至少一次所需的最小行驶距离。

输入格式

输入按照下述格式从标准输入给出： $N$ $A_1$ $B_1$ $C_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$

输出格式

输出答案。

4
1 2 2
1 3 3
1 4 4

11

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

9000000000

提示

$2 \leq N \leq 2\times 10^5$ $1 \leq A_i, B_i \leq N$ $1 \leq C_i \leq 10^9$ 所有输入值均为整数。 任意一对城市之间都可以通过若干道路互相到达。如果按 $4 \to 1 \to 2 \to 1 \to 3$ 行驶，总行驶距离为 $11$，这是最小值。 注意不需要返回出发城市。
注意可能的溢出。

标签: AtCoder|abc361E

来源

AtCoder|abc361E