#112 Tree Operation

Loading problem...

Preparing the statement, recent submissions, and submit form.

#112 Tree Operation | DOJ

Authors: dyppp

Statement

정점이 $N$ 개인 트리가 주어진다. 처음에 각 정점에는 $0$ 이 적혀 있다.

당신은 각 정점에 대해 최대 한 번씩 다음 시행을 할 수 있다.

정점 하나를 고른 후, 그 정점에 적힌 수를 인접한 정점에 적힌 수 중 가장 작은 수 $+1$ 로 바꾼다.

만약 고른 정점에 인접한 정점이 없다면, 인접한 정점에 적힌 수 중 가장 작은 수는 $0$ 으로 간주한다.

시행들을 적절한 순서로 수행했을 때, 트리에 적힌 수들의 합의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

주어지는 그래프는 $N$ 개의 정점을 가진 트리이다. 정점은 $1$ 번부터 $N$ 번까지 번호가 매겨져 있다.

트리에 적힌 수들의 합의 최댓값을 출력한다.

#	Score	Constraints
1	100	전체 제약을 만족하는 테스트입니다.

Sample 1

Input

Output

유일한 정점에 시행을 하면 적힌 수가 $1$ 이 된다.

Sample 2

Input

3
1 2
2 3

Output

먼저 $2$ 번 정점에 시행을 하면 $1$ 이 된다. 이후 $1$ 번, $3$ 번 정점에 시행을 하면 두 정점은 각각 $2$ 가 된다. 합은 $2+1+2=5$ 이다.

Sample 3

Input

Output

$1$ 번 정점에 먼저 시행을 하면 $1$ 이 된다. 이후 $2,3,4$ 번 정점에 시행을 하면 세 정점은 각각 $2$ 가 된다. 합은 $7$ 이다.