Minequake

Time limit2sMemory limit1024 MB

Summary

Given a tree of n halls, start anywhere and visit every hall, minimizing the sum of the arrival times at each hall.

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

Problem

The fully autonomous microbreweries installed in the abandoned Dwarven mines of Moravia are a showcase of Dwarven engineering. Earthquakes sometimes shake the mines, misaligning pipes and funnels so that liquid spills onto the floor. As the Exalted Warden of Brewery Safety, you must turn off the machines in every hall when an earthquake strikes.

Walking through tunnels takes time, so you will arrive late at many of the machines. You cannot avoid this, but you want to minimise the total amount of spilled liquid.

The mines consist of $n$ halls connected by $n-1$ tunnels. The whole system is connected, so you can get from any hall to any other hall. Traversing a tunnel takes 1 unit of time. Switching off machines and traversing a hall takes no time. If you turn off the machines in a hall $t$ units of time after the earthquake, $t$ liters of liquid spill. There is exactly one earthquake, and it affects all halls at the same time. You may not switch off any machines before the earthquake. You can start in any hall.

The following figure shows the layout of the mines for the first sample.

Input

The first line contains the integer $n$ , the number of halls. The halls are numbered $1$ to $n$ . Each of the next $n-1$ lines contains two space-separated integers $u$ and $v$ with $1 \le u < v \le n$ , meaning that a tunnel connects hall $u$ and hall $v$ .

Output

Print a single integer: the minimum amount of spilled liquid, in liters.

Constraints

We always have $1 \le n \le 10^5$ .

Examples3

Example 1
Input
```
3
1 2
2 3
```
Expected output
```
3
```
Example 2
Input
```
4
1 2
1 3
1 4
```
Expected output
```
7
```
Example 3
Input
```
1
```
Expected output
```
0
```