짧은 무작위 문제

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

요약

간선 길이가 0과 1 사이의 독립적인 균등 분포 실수인 트리가 주어질 때, 지름의 기댓값을 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 9점
유형: 트리, 확률, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

이 대회에는 이 문제 말고도 풀 문제가 많으니 짧게 가겠다.

$n$ 개의 정점으로 이루어진 트리가 주어진다. 각 간선의 길이는 0과 1 사이의 실수 중에서 서로 독립적으로, 균등한 확률로 무작위 선택된다. 이 트리 지름의 기댓값을 구하라.

입력

첫 줄에 정점의 개수를 나타내는 정수 $n$ ( $2 \leq n \leq 100$ )이 주어진다.

다음 $n-1$ 개 줄에는 $i$ 번째 간선의 양 끝점을 나타내는 정수 $u_i$ , $v_i$ ( $1 \leq u_i, v_i \leq n$ , $u_i \neq v_i$ )가 한 줄에 하나씩 주어진다.

출력

답을 $10^9 + 7$ 로 나눈 값으로 출력한다. 기댓값은 서로소인 정수 $p$ , $q$ 에 대해 $\frac{p}{q}$ 로 나타낼 수 있는 유리수이며, $q$ 는 $10^9 + 7$ 로 나누어떨어지지 않는다. $p - aq$ 가 $10^9 + 7$ 의 배수가 되도록 하는 0 이상 $10^9 + 6$ 이하의 정수 $a$ 를 출력한다.

예제2

예제 1
입력
```
5
1 2
2 3
3 4
4 5
```
예상 출력
```
2
```
예제 2
입력
```
5
4 2
2 3
3 1
3 5
```
예상 출력
```
283333337
```