题目背景

ICPC2020 WF J

题目描述

The Yllihc Engineering and Technological Institute (YETI), located in upper northern Snowblovia, has two problems: snow and money. Specifically, they have too much of the former and not enough of the latter. Every winter (and fall and spring for that matter) the campus is covered with blankets of snow. The maintenance staff must clear all the sidewalks connecting the campus buildings, but they have only two snow blowers and have been told in no uncertain terms that they cannot expect to obtain any more in the near future.

To preserve the longevity of these two precious machines, the staff has decided on the following snow removal procedure. Each machine is assigned a fixed route connecting two of the buildings on campus. Whenever snow must be removed, each snow blower is taken from the building at one end of its route and used to clear snow, ending up in the building at the other end of its route, where it is stored until the next snowfall. The reverse movement will occur during the next snow removal event---each machine will trace its assigned route in the opposite direction. This process cycles throughout the eleven-month snow season. Note that a route might involve doubling back over sidewalks that have already been cleared. Also, it is possible that the same building might be an endpoint for both snow blower routes.

The campus sidewalks are laid out in the form of a tree. To run the machines as little as possible, the staff wants to minimize the total distance that the snow blowers must travel as they are guided along their routes. Figure J.1 shows an optimal solution for the sidewalk layout of the first sample input.

The YETI maintenance crew would ask the Computer Science Department at YETI to figure this out, but they were wiped out in the Great Blizzard of '$06$, so they have come to you for help.

输入格式

The first line of input contains an integer $n$ ($4\leq n\leq 100\,000$), the number of buildings on the YETI campus. Buildings are numbered from $1$ to $n$. Each of the remaining $n-1$ lines contains three integers $a$, $b$, and $d$ indicating that a two-way sidewalk exists between buildings $a$ and $b$ ($1 \leq a, b \leq n$; $a\ne b$) of length $d$ ($1\leq d\leq 500$).

输出格式

Output the minimum total distance the two machines must travel in any snow removal event.

题目大意

题目描述

位于斯诺布洛维亚北部的 某·工程技术学院 (YETI) 面临两个问题：雪和金钱。具体来说，他们有太多的前者而没有足够的后者。每年冬天（以及秋天和春天），校园都覆盖着雪毯。维护人员必须清理连接校园建筑的所有人行道，但他们只有两台吹雪机，并且已经明确告知他们在不久的将来不能再获得更多。

为了保持这两台珍贵机器的使用寿命，工作人员决定采用以下除雪程序。每台机器都被分配了一条连接校园内两座建筑物的固定路线。每当必须除雪时，每台吹雪机都会从其路线一端的建筑物中取出并用于清除积雪，最终进入其路线另一端的建筑物中，并存放在那里直到下一次降雪。在下一次除雪活动期间将发生反向运动——每台机器将沿相反方向追踪其分配的路线。这个过程在整个 1 个月的雪季循环。请注意，路线可能涉及翻过已清理的人行道。此外，同一建筑物可能是两条吹雪机路线的终点。

校园人行道以树的形式布置。为了尽可能少地运行机器，工作人员希望尽量减少吹雪机在沿路线引导时必须行驶的总距离。图 J.1 显示了第一个样本输入的人行道布局的最佳解决方案。

YETI 维护人员会要求 YETI 的计算机科学系解决这个问题，但他们在 06 年的大暴雪中失败了，所以他们来找你帮忙。

输入格式

输入的第一行包含一个整数 n(4≤n≤100000)，即 YETI 校园内的建筑物数量。 建筑物的编号从 1 到 n。其余n−1 行中的每一行包含三个整数 a、b和d，表示建筑物 a和 b之间存在双向人行道 (1≤a,b≤n) 长度为 d(1≤d≤500)。

输出格式

输出两台机器在任何除雪事件中必须行驶的最小总距离。

7
1 4 2
2 4 3
3 4 1
4 5 1
5 6 2
5 7 4

15

4
1 2 1
2 3 2
3 4 3

6