← 返回题目列表

AtCoder · agc018_d

D. 树和汉密尔顿路径

中文机器翻译题面 查看原题

分数: 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