Gems

Interview

Time limit1sMemory limit128 MB

Summary

Given a tree, assign positive integer prices to vertices so adjacent vertices differ, minimizing total sum, essentially a greedy coloring based on tree structure.

Level: Medium5 of 10
Topics: Tree, Greedy, DFS
Solved: No attempts yet

Problem

The Gem-Toys Company has asked you to solve the following problem.

You are given a connected acyclic graph — a tree — a set of vertices joined by edges so that every vertex can reach every other vertex, with no cycle.

The company will manufacture jewelry models shaped like such trees: each vertex is a gem and each edge is a piece of gold string. Two adjacent vertices must be made of different kinds of gems. For every positive integer $p$ there is exactly one kind of gem, and its price is $p$ .

Compute the minimum total price of the gems needed to build the model.

Input

The first line contains one integer $N$ ( $1 \le N \le 10\,000$ ), the number of vertices, numbered from $1$ to $N$ .

Each of the next $N-1$ lines contains two integers $A$ and $B$ ( $1 \le A, B \le N$ , $A \ne B$ ) describing an edge between vertices $A$ and $B$ .

Output

Print a single integer: the minimum total price of the gems needed to build the model.

Examples6

Example 1
Input
```
8
1 2
3 1
1 4
5 6
1 5
5 7
5 8
```
Expected output
```
11
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
2
1 2
```
Expected output
```
3
```
Example 4
Input
```
3
1 2
2 3
```
Expected output
```
4
```
Example 5
Input
```
5
1 2
1 3
1 4
1 5
```
Expected output
```
6
```
Example 6
Input
```
8
1 2
1 3
1 4
1 5
1 6
5 7
6 8
```
Expected output
```
11
```