정다각형을 만들어요

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

요약

트리에서 서로 다른 두 개 이상의 정점을 골라 모든 정점과의 거리가 같은 정점이 정확히 하나뿐인 집합의 개수를 세어 10^9+7로 나눈 나머지를 구한다.

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

문제

호반우는 $1$ 번부터 $N$ 번까지 번호가 매겨진 정점이 $N$ 개인 트리에서 정다각형을 찾으려고 한다.

트리에서의 정다각형이란 서로 다른 $2$ 개 이상의 정점을 선택하였을 때 선택한 정점 모두와 거리가 같은 정점이 단 하나만 존재한다면 선택한 정점의 집합을 정다각형이라 부른다. 두 정점 사이의 거리란, 한 정점과 다른 정점을 잇는 유일한 단순 경로 위의 간선의 개수로 정의한다.

정다각형을 하나하나 세고 있는 호반우를 위해 트리에서 서로 다른 정다각형이 몇 개나 있는지 알려주자.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다. $(1 \leq N \leq 2\\,000)$

둘째 줄부터 $N - 1$ 개의 줄에 걸쳐 트리의 각 간선이 잇는 두 정점의 번호 $u, v$ 가 공백을 두고 주어진다. $(1 \leq u < v \leq N)$

출력

첫째 줄에 주어진 트리에서 정다각형의 개수를 출력한다. 단, 수가 매우 커질 수 있으므로 $10^{9} + 7$ 로 나눈 나머지를 출력한다.

예제2

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