시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB68318711225.806%

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있다.

서로 다른 두 개의 정점을 균일한 확률로 랜덤하게 선택했을 때, 거리가 소수일 확률은 몇일까?

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다.

출력

서로 다른 두 개의 정점을 균일한 확률로 랜덤하게 선택했을 때, 거리가 소수일 확률을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1

5
1 2
2 3
3 4
4 5

예제 출력 1

0.5

출처