등산 마니아

시간 제한2초메모리 제한512 MB

요약

1번 정점을 뿌리로 하는 트리에서 모든 쌍 (i,j)에 대해, 뿌리를 지나는 최단 경로가 포함하는 서로 다른 간선 수의 합을 구한다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

동네 뒷산에 등산로가 있다. 등산로는 $N$ 개의 작은 오두막이 $N-1$ 개의 오솔길로 이어진 형태이다. 한 오솔길은 두 오두막을 양방향으로 연결하며 길이는 1이다. 어떤 오두막에서도 오솔길만 따라가면 다른 모든 오두막에 도달할 수 있다. 오두막에는 1번부터 $N$ 번까지 번호가 붙어 있고, 1번 오두막이 산 정상에 있다. 1번 오두막에서 다른 오두막으로 가는 최단 경로에 포함된 모든 오솔길은 항상 산을 내려가는 방향이다.

철수는 등산 마니아이다. 철수가 한 오두막에서 다른 오두막으로 갈 때는 항상 산 정상을 거치는 최단 경로를 따라간다. 이때 길의 다양성은 경로에 포함된 오솔길의 개수로 정의한다. 두 번 이상 지나간 오솔길은 한 번만 센다는 점에 주의하라.

아래 그림은 가능한 하나의 상황을 보여 준다. 산 정상에 1번 오두막이 있고 3번 오두막과 4번 오두막이 오솔길로 이어져 있다.

아래 그림은 2번 오두막에서 7번 오두막으로 가는 최단 경로를 보여 준다.

아래 그림은 2번 오두막에서 7번 오두막으로 정상을 거쳐 가는 최단 경로를 보여 준다.

등산로의 구성을 입력으로 받아, 모든 $1 \le i < j \le N$ 인 쌍 $(i, j)$ 에 대해 철수가 $i$ 번 오두막에서 $j$ 번 오두막으로 갈 때의 길의 다양성의 총합을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 $N$ 이 주어진다. 다음 $N-1$ 개의 줄에 오두막 번호 두 개가 공백 하나를 사이에 두고 주어진다. 두 오두막이 오솔길로 이어져 있다는 뜻이다.

출력

첫 번째 줄에 문제의 정답을 출력한다.

제한

$2 \le N \le 300\,000$

예제2

예제 1
입력
```
3
1 2
2 3
```
예상 출력
```
5
```
예제 2
입력
```
8
6 2
7 5
3 4
5 6
1 5
4 1
8 6
```
예상 출력
```
84
```