힙

정점이 n개이고 1을 루트로 하는 트리가 주어진다.

다음 조건을 만족하면 u에 깊이 m의 k진 힙이 있다고 한다.

• m = 1인 경우, u 자체가 깊이 1의 k진 힙이다.
• m > 1인 경우, u의 자식 중 적어도 k개가 깊이가 적어도 m - 1인 k진 힙이면 정점 u는 깊이 m의 k진 힙이다.

dpk(u)를 u를 포함한 u의 서브트리에 있는 k진 힙의 최대 깊이라고 하자. 목표는 를 계산하는 것이다.

첫 번째 줄에는 트리 (2 ≤ n ≤ 3·105)의 크기를 나타내는 정수 n가 주어진다.

다음 n - 1개의 줄에는 각각 두 정수 u, v가 주어지며, 이는 i-th 간선으로 연결된 정점들을 나타낸다.

주어진 구성이 트리를 이룬다는 것이 보장된다.

문제의 답을 출력한다.

첫 번째 예제를 살펴보자.

k ≥ 3이면 모든 dpk는 1과 같다.

k = 2이면 일 때 dpk는 2이고, 그렇지 않으면 1이다.

k = 1이면 dpk 값은 각각 (3, 1, 2, 1)이다.

모두 합하면 4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21이다.