숭고한 마라톤 대회

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

요약

교차로 N개로 이루어진 트리에 도로를 정확히 두 개 추가하여, 두 교차로 사이에 중간 교차로를 공유하지 않는 경로가 세 개 생기는 방법의 수를 구합니다.

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

문제

숭고한 연합은 알고리즘 마라톤 대회를 열기 위해 적당한 장소를 골랐다. 이 장소는 $N$ 개의 교차로와 $N-1$ 개의 양방향 도로로 이루어져 있고, 서로 다른 모든 교차로 쌍 사이에 경로가 정확히 하나 존재한다. (즉, 이 장소는 트리 구조이다.)

알고리즘 마라톤이니만큼 주자들이 머릿속으로 최단 경로 알고리즘을 돌리면서 달릴 수 있는 코스가 다양하면 좋다. 그래서 서로 다른 두 교차로를 골라 하나는 시작 교차로, 다른 하나는 끝 교차로로 정한다. 목표는 숭실대, 고려대, 한양대 세 학교가 각각 시작 교차로에서 끝 교차로까지 가는 경로를 하나씩 정할 수 있도록 하는 것이다. 이때 세 경로는 시작 교차로와 끝 교차로를 제외하고 공유하는 교차로가 없어야 한다.

방법 1의 경우: 2를 시작 교차로, 3을 끝 교차로로 정하면 겹치지 않는 세 경로가 생긴다.

방법 2의 경우: 1을 시작 교차로, 2를 끝 교차로로 정하면 겹치지 않는 세 경로가 생긴다.

방법 3의 경우: 2를 시작 교차로, 4를 끝 교차로로 정하면 겹치지 않는 세 경로가 생긴다.

따라서 주어진 트리에서 가능한 방법은 3가지이고, 정답은 3이다.

목표를 달성할 수 있도록 장소에 도로를 정확히 2개 추가한다. 어떤 도로를 추가할지 정하는 방법이 몇 가지인지 구하라. 방법의 수가 클 수 있으므로 $10^9+7$ 로 나눈 나머지를 출력한다. 도로를 추가한 뒤에도 두 교차로 사이의 도로는 최대 하나뿐이어야 하고, 양 끝 교차로가 같은 도로는 있을 수 없다. (즉, 단순 그래프여야 한다.)

입력

첫 번째 줄에 교차로의 개수 $N$ 이 주어진다. ( $4 \le N \le 500{,}000$ )

두 번째 줄부터 $N-1$ 개의 줄에 걸쳐 각 도로가 연결하는 두 교차로의 번호 $a$ , $b$ 가 공백으로 구분되어 주어진다. ( $1 \le a, b \le N$ )

주어지는 입력은 트리임이 보장된다.

출력

목표를 달성할 수 있도록 도로 2개를 정하는 방법의 수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제4

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

예제 4

입력

예상 출력