Add One Zero-Weight Edge to Minimize the Sum of Root Distances

Time limit2sMemory limit1024 MB

Summary

Given a weighted tree rooted at vertex 1, add one zero-weight edge to minimize the sum of root distances and print that minimum.

Level: Hard8 of 10
Topics: Tree, DFS, Dynamic programming
Solved: No attempts yet

문제

A tree is a simple connected graph with no cycles.

You are given a tree with $N$ vertices. The vertices are numbered from 1 to $N$ . The root of the tree is always vertex 1, and every edge has a positive weight.

You may use the following operation at most once.

Add an edge of weight $0$ between any two vertices $u$ and $v$ .

Let $d_i$ be the shortest distance from vertex $i$ to the root vertex. Using the operation exactly once, write a program that minimizes $\sum_{i=1}^{N} d_i$ .

입력

The first line contains the number of vertices $N$ . $(1\leq N\leq 200\,000)$

Each of the next $N-1$ lines contains three integers $u$ , $v$ , and $w$ , separated by spaces, describing an edge between $u$ and $v$ with weight $w$ . $(1\leq u,v\leq N;$ $1\leq w\leq 1\,000\,000)$

출력

Print the minimum possible value of $\sum_{i=1}^{N} d_i$ .

Examples2

Example 1
Input
```
3
1 2 3
1 3 4
```
Expected output
```
3
```
Example 2
Input
```
6
5 4 10
2 5 3
6 4 9
3 6 8
1 6 6
```
Expected output
```
33
```