分数: 1100 点
问题陈述
有一棵树 N 顶点,编号 1 通过 N。 的 i此树中的第一条边连接顶点 A_i 和 B_i 的长度为 C_i.
Joisino 创建了一个完整的图表 N 顶点。 连接顶点的边的长度 该图中的 u 和 v 等于顶点之间的最短距离 u 和 v 在上面的树中。
Joisino 想知道这个完整图中最长哈密顿路径的长度(参见注释)。 求该路径的长度。
注释
A 哈密顿路径 图中的 是图中仅访问每个顶点一次的路径。
约束
- 2 \leq N \leq 10^5
- 1 \leq A_i < B_i \leq N
- 给定的图是一棵树。
- 1 \leq C_i \leq 10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{N-1} B_{N-1} C_{N-1}
输出
打印 Joisino 创建的完整图中最长哈密顿路径的长度。
示例输入 1
5 1 2 5 3 4 7 2 3 3 2 5 2
示例输出 1
38
哈密顿路径的长度 5 → 3 → 1 → 4 → 2 is 5+8+15+10=38。由于不存在长度为 的哈密顿路径 图中的 39 或更大,答案是 38.
示例输入 2
8 2 8 8 1 5 1 4 8 2 2 5 4 3 8 6 6 8 9 2 7 12
示例输出 2
132