Journey
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: dp, trees

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.

Input format:
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 format:
Output one integer, which represents the minimum time in hours that is needed to visit each city at least once.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
4
1 2 4
2 3 5
3 4 4

Example output:
8

Example input:
5
1 2 45
1 3 50
1 4 10
1 5 65

Example output:
115

Editorial:
For a journey, define $$$\text{cnt}(i)$$$ as a non-negative integer representing the number of times Pak Chanek traverses road $$$i$$$ throughout the journey.
First, let's solve the simpler problem where we cannot teleport. It can be obtained that the configuration of $$$\text{cnt}(i)$$$ for an optimal journey in this version of the problem is as follows:
• The roads with $$$\text{cnt}(i)=1$$$ form a simple path.
• Every other road outside of the path has $$$\text{cnt}(i)=2$$$.
If we add the ability to teleport at most once, the configuration of $$$\text{cnt}(i)$$$ is similar, but the roads with $$$\text{cnt}(i)=1$$$ form two distinct simple paths, with both paths not containing any common roads. Let's denote these two paths as $$$P_1$$$ and $$$P_2$$$.
Notice that $$$P_1$$$ and $$$P_2$$$ can only have either one common city or no common cities at all. It can be obtained that the optimal configuration for each case is as follows:
• If $$$P_1$$$ and $$$P_2$$$ have one common city, every other road outside of $$$P_1$$$ and $$$P_2$$$ must have $$$\text{cnt}(i)=2$$$.
• If $$$P_1$$$ and $$$P_2$$$ have no common cities, we have the opportunity to pick one road in the path between $$$P_1$$$ and $$$P_2$$$ and assign $$$\text{cnt}(i)=0$$$. Then, every other road must have $$$\text{cnt}(i)=2$$$.
It can be shown that for any configuration of $$$\text{cnt}(i)$$$ satisfying the constraints above, there always exists a valid journey that corresponds to that configuration. So we must find the configuration that results in the minimum time for each case.
For the first case, we can precompute a tree DP with rerooting and try each possible common city to get the optimal answer. For the second case, we can also precompute a tree DP with rerooting and try each possible road with $$$\text{cnt}(i)=0$$$ to get the optimal answer.