평균 거리

면접 대비

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

요약

가중치가 있는 트리에서 모든 두 정점 쌍 사이 거리의 평균을 1e-6 오차 이내로 구한다.

난이도: 보통10점 중 6점
유형: 트리, DFS, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

트리가 주어질 때, 트리에서 두 정점 사이의 평균 거리를 구하라. 예를 들어 다음 트리에서 두 정점 사이의 평균 거리는 (d01 + d02 + d03 + d04 + d12 + d13 + d14 + d23 + d24 + d34)/10 = (6 + 3 + 7 + 9 + 9 + 13 + 15 + 10 + 12 + 2)/10 = 8.6이다.

그림 1: 첫 번째 예시

입력

첫째 줄에 정수 t (1 ≤ t ≤ 100)가 주어진다. 이는 테스트 케이스의 수이다. 그다음 각 테스트 케이스마다:

정수 n (2 ≤ n ≤ 10 000)이 있는 한 줄이 주어진다. 이는 트리의 정점 수이다. 정점은 0부터 n − 1까지 번호가 매겨진다.
n − 1개의 줄이 주어지며, 각 줄에는 세 정수 a (0 ≤ a < n), b (0 ≤ b < n), d (1 ≤ d ≤ 1 000)가 있다. 번호가 a와 b인 정점 사이에 길이 d인 간선이 있다. 만들어진 그래프는 트리이다.

출력

각 테스트 케이스마다:

두 정점 사이의 평균 거리를 한 줄에 출력한다. 이 값의 절대 오차 또는 상대 오차는 10−6 이하여야 한다.

예제1

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