#112 Tree Operation

Loading problem...

Preparing the statement, recent submissions, and submit form.

#112 Tree Operation | DOJ

Authors: dyppp

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

KO EN

You are given a tree with $N$ vertices. Initially, the number written on every vertex is $0$ .

For each vertex, you may perform the following operation at most once.

Choose one vertex and change the number written on it to the minimum number written on an adjacent vertex, plus $1$ .

If the chosen vertex has no adjacent vertices, the minimum number among adjacent vertices is considered to be $0$ .

Find the maximum possible sum of all numbers written on the tree after performing operations in a suitable order.

Input

The input is given in the following format.

$N$ $u_1\ v_1$ $u_2\ v_2$ $\cdots$ $u_{N-1}\ v_{N-1}$

The given graph is a tree with $N$ vertices. The vertices are numbered from $1$ to $N$ .

Output

Print the maximum possible sum of all numbers written on the tree.

Constraints

$1 \le N \le 200\,000$ .
$1 \le u_i, v_i \le N$ .
$u_i \ne v_i$ .
The given graph is a tree.

Subtasks

#	Score	Constraints
1	100	Full constraints.

Samples

Sample 1

Input

Output

Performing the operation on the only vertex changes its number to $1$ .

Sample 2

Input

3
1 2
2 3

Output

First perform the operation on vertex $2$ , making it $1$ . Then perform the operation on vertices $1$ and $3$ , making both of them $2$ . The sum is $2+1+2=5$ .

Sample 3

Input

Output

First perform the operation on vertex $1$ , making it $1$ . Then perform the operation on vertices $2,3,4$ , making all three of them $2$ . The sum is $7$ .

Editorial

View editorial