頁面無法載入？點擊這裡可能會修復。
Placeholder

#10463
評測保留

필수 고가도로 20s 2048MB

問題

에키야(Ekiya)의 마을에 세워진 현대적인 철도 시스템이 큰 난관에 부딪혔다: 남북 방향으로 뻗은 주요 고속도로이다. 고속도로 서쪽에는 이미 \mathbf{W}개의 역이 건설되어 서로 연결되어 있고, 동쪽에는 \mathbf{E}개의 역이 건설되어 연결되어 있다. 서쪽의 한 역과 동쪽의 한 역을 잇는 연결이 하나 더 필요하지만, 고속도로가 가로막고 있으므로 그 연결은 고가도로(overpass)를 이용해 건설해야 한다.

에키야는 고가도로로 어떤 역들을 연결하는 것이 가장 편리할지 평가하고 있다. 그 평가의 일환으로, 가능한 각 선택지마다 시스템 안에서의 경로의 평균 길이(지나는 역의 수 기준)가 어떻게 달라지는지 알고 싶다.

역 s와 t 사이의 경로란, 서로 다른 역들의 목록으로서 s로 시작해 t로 끝나며, 목록에서 이웃한 두 역이 연결을 공유하는 것을 말한다. 현재 철도 시스템의 서쪽에는 \mathbf{W}개의 역이 있고, \mathbf{W}-1개의 연결로 이어져 있어 서로 다른 임의의 두 서쪽 역 사이의 경로가 정확히 하나뿐이다. 동쪽도 마찬가지로, \mathbf{E}개의 동쪽 역이 \mathbf{E}-1개의 연결로 이어져 있어 서로 다른 임의의 두 동쪽 역 사이의 경로가 정확히 하나뿐이다. 서쪽의 한 역과 동쪽의 한 역을 잇는 고가도로 연결이 건설되면, 서로 다른 임의의 두 역 사이의 경로도 정확히 하나가 된다.

완전한 지도(complete map)란 총 연결 수가 \mathbf{W}+\mathbf{E}-1이고, 서로 다른 임의의 두 역 사이의 경로가 정확히 하나인 지도이다. 완전한 지도의 평균 거리(average distance)는 서로 다른 모든 역 쌍 사이 경로 길이의 평균이다. 경로의 길이는 그 경로를 정의하는 역 목록의 길이보다 1 작다. (예를 들어 직접 연결된 두 역 사이의 경로 길이는 1이다.)

예를 들어, 아래 그림은 서쪽에 \mathbf{W} = 2개의 역이 있고 동쪽에 \mathbf{E} = 3개의 역이 있는 상황을 보여 준다. 가능한 고가도로는 2개가 있다.

Illustration of Sample Case #1

다음 표는 각 고가도로를 건설했을 때 역 쌍 사이 경로의 길이를 보여 준다.

\color{darkred}{\mathbf{1 \leftrightarrow 1}}\color{darkblue}{\mathbf{2 \leftrightarrow 3}}
서쪽 1서쪽 211
서쪽 1동쪽 113
서쪽 1동쪽 233
서쪽 1동쪽 322
서쪽 2동쪽 122
서쪽 2동쪽 242
서쪽 2동쪽 331
동쪽 1동쪽 222
동쪽 1동쪽 311
동쪽 2동쪽 311
평균:21.8

현재 역들과 기존 연결, 그리고 고가도로 연결의 선택지 목록이 주어질 때, 각 선택지를 유일한 고가도로로 추가했을 경우 만들어지는 지도의 평균 거리를 계산하여 에키야를 도와주자.


輸入

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 정수 세 개 \mathbf{W}, \mathbf{E}, \mathbf{C}가 주어진 한 줄로 시작한다. 이는 각각 서쪽 역의 수, 동쪽 역의 수, 그리고 고가도로 연결에 대한 선택지의 수이다. 서쪽 역은 1부터 \mathbf{W}까지 번호가 매겨져 있고, 동쪽 역은 1부터 \mathbf{E}까지 번호가 매겨져 있다.

테스트 케이스의 둘째 줄에는 \mathbf{W}-1개의 정수 \mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_{W-1}}가 주어진다. 이는 서쪽 역들 사이의 i번째 기존 연결이 서쪽 역 i와 서쪽 역 \mathbf{X_i}를 잇는다는 뜻이다.

테스트 케이스의 셋째 줄에는 \mathbf{E}-1개의 정수 \mathbf{F_1}, \mathbf{F_2}, \dots, \mathbf{F_{E-1}}가 주어진다. 이는 동쪽 역들 사이의 j번째 기존 연결이 동쪽 역 j와 동쪽 역 \mathbf{F_j}를 잇는다는 뜻이다.

마지막으로 테스트 케이스의 다음 \mathbf{C}줄은 고가도로 연결의 선택지들을 나타낸다. 이 중 k번째 줄에는 정수 두 개 \mathbf{A_k}, \mathbf{B_k}가 주어지며, 이는 k번째 고가도로 선택지가 서쪽 역 \mathbf{A_k}와 동쪽 역 \mathbf{B_k}를 잇는다는 뜻이다.


輸出

각 테스트 케이스마다 Case #x: y_1 ~ y_2 ~ \cdots ~ y_{\mathbf{C}} 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y_k는 k번째 선택지를 고가도로 연결로 추가했을 때(기존 연결들은 모두 유지) 만들어지는 지도의 평균 거리이다.

y_1, y_2, \dots 및 y_k는 정답과의 절대 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지, 그리고 어떤 실수 형식이 허용되는지에 대해서는 FAQ를 참고하라.


範例 

3
2 3 2
2
3 3
1 1
2 3
3 4 2
2 3
3 3 4
1 3
1 2
3 4 1
2 3
3 3 4
2 2
Case #1: 2.0 1.8
Case #2: 2.19047619 2.47619048
Case #3: 2.2857142857
샘플 케이스 #1은 문제 설명에 설명 및 그림이 있다. 샘플 케이스 #2와 #3은 아래에 그림으로 제시되어 있다.

來源

GCJ 2023d A

需要登入才能撰寫程式碼。