Journey

题意翻译

给你一棵树，边有边权，要求从任意一点出发遍历这棵树，经过每一个节点**至少**一次（起始点和终止点**不必**相同）。你可以**至多一次**从一点传送到另一点（传送经过的路程不计）。问可以走过的最小的总边权是多少。 输入数据第一行一个正整数n，表示这棵树有n个节点，从1-n编号。以下n-1行给出u,v,w，表示一条连接点u，v，权值为w的树边。

题目描述

One day, Pak Chanek who is already bored of being alone at home decided to go traveling. While looking for an appropriate place, he found that Londonesia has an interesting structure. According to the information gathered by Pak Chanek, there are $ N $ cities numbered from $ 1 $ to $ N $ . The cities are connected to each other with $ N-1 $ two-directional roads, with the $ i $ -th road connecting cities $ U_i $ and $ V_i $ , and taking a time of $ W_i $ hours to be traversed. In other words, Londonesia's structure forms a tree. Pak Chanek wants to go on a journey in Londonesia starting and ending in any city (not necessarily the same city) such that each city is visited at least once with the least time possible. In order for the journey to end quicker, Pak Chanek also carries an instant teleportation device for moving from one city to any city that can only be used at most once. Help Pak Chanek for finding the minimum time needed. Notes: - Pak Chanek only needs to visit each city at least once. Pak Chanek does not have to traverse each road. - In the journey, a city or a road can be visited more than once.

输入输出格式

输入格式

The first line contains a single integer $ N $ ( $ 1 \le N \le 10^5 $ ) — the number of cities in Londonesia. The $ i $ -th of the next $ N-1 $ lines contains three integers $ U_i $ , $ V_i $ , and $ W_i $ ( $ 1 \le U_i, V_i \le N $ , $ 1 \le W_i \le 10^9 $ ) — a two-directional road that connects cities $ U_i $ and $ V_i $ that takes $ W_i $ hours to be traversed. The roads in Londonesia form a tree.

输出格式

Output one integer, which represents the minimum time in hours that is needed to visit each city at least once.

输入输出样例

输入样例 #1

4
1 2 4
2 3 5
3 4 4

输出样例 #1

8

输入样例 #2

5
1 2 45
1 3 50
1 4 10
1 5 65

输出样例 #2

115

说明

In the first example, the journey that has the minimum time is $ 2 → 1 \xrightarrow{\text{teleport}} 4 → 3 $ . In the second example, the journey that has the minimum time is $ 3 → 1 → 4 → 1 → 2 \xrightarrow{\text{teleport}} 5 $ .

题目大意：
给你一棵树，边有边权，要求从任意一点出发遍历这棵树，经过每一个节点至少一次（起始点和终止点不必相同）。你可以至多一次从一点传送到另一点（传送经过的路程不计）。问可以走过的最小的总边权是多少。

输入数据第一行一个正整数n，表示这棵树有n个节点，从1-n编号。以下n-1行给出u,v,w，表示一条连接点u，v，权值为w的树边。

输入输出格式：
输入格式：
- 第一行包含一个整数N（1≤N≤10^5）——Londonesia的城市的数量。
- 接下来的N-1行，每行包含三个整数U_i, V_i, 和 W_i（1≤U_i, V_i≤N，1≤W_i≤10^9）——连接城市U_i和V_i的双向道路，需要W_i小时才能通过。Londonesia的道路形成了一棵树。

输出格式：
- 输出一个整数，表示至少访问一次每个城市所需的最小时间（小时）。

输入输出样例：
输入样例 #1：
```
4
1 2 4
2 3 5
3 4 4
```
输出样例 #1：
```
8
```
输入样例 #2：
```
5
1 2 45
1 3 50
1 4 10
1 5 65
```
输出样例 #2：
```
115
```

说明：
在第一个例子中，时间最少的旅程是 2 → 1 → (传送) → 4 → 3。
在第二个例子中，时间最少的旅程是 3 → 1 → 4 → 1 → 2 → (传送) → 5。题目大意： 给你一棵树，边有边权，要求从任意一点出发遍历这棵树，经过每一个节点至少一次（起始点和终止点不必相同）。你可以至多一次从一点传送到另一点（传送经过的路程不计）。问可以走过的最小的总边权是多少。 输入数据第一行一个正整数n，表示这棵树有n个节点，从1-n编号。以下n-1行给出u,v,w，表示一条连接点u，v，权值为w的树边。 输入输出格式： 输入格式： - 第一行包含一个整数N（1≤N≤10^5）——Londonesia的城市的数量。 - 接下来的N-1行，每行包含三个整数U_i, V_i, 和 W_i（1≤U_i, V_i≤N，1≤W_i≤10^9）——连接城市U_i和V_i的双向道路，需要W_i小时才能通过。Londonesia的道路形成了一棵树。 输出格式： - 输出一个整数，表示至少访问一次每个城市所需的最小时间（小时）。 输入输出样例： 输入样例 #1： ``` 4 1 2 4 2 3 5 3 4 4 ``` 输出样例 #1： ``` 8 ``` 输入样例 #2： ``` 5 1 2 45 1 3 50 1 4 10 1 5 65 ``` 输出样例 #2： ``` 115 ``` 说明： 在第一个例子中，时间最少的旅程是 2 → 1 → (传送) → 4 → 3。 在第二个例子中，时间最少的旅程是 3 → 1 → 4 → 1 → 2 → (传送) → 5。