#P12961. [GCJ Farewell Round #4] Indispensable Overpass

    ID: 12763 Type: RemoteJudge 20000~40000ms 2048MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>2023Special Judge树形 DPGoogle Code Jam

[GCJ Farewell Round #4] Indispensable Overpass

题目描述

A modern railroad system built in Ekiya's town bumped into a major hurdle: the main freeway running north to south. W\mathbf{W} stations have already been built and connected on the western side of the freeway and E\mathbf{E} on the eastern side. One more connection is needed between a western and an eastern station, but because the freeway is in the way, that connection needs to be built using an overpass.

Ekiya is assessing which stations would be most convenient to connect with the overpass. As part of that assessment, she wants to know how the average length (in number of stations) of a path within the system might change with each possible option.

A path between stations ss and tt is a list of distinct stations that starts with ss, ends with tt, and such that any two consecutive stations on the list share a connection. The railroad system currently has W\mathbf{W} stations on the western side, connected through W1\mathbf{W}-1 connections such that there is exactly one path between any two distinct western stations. Similarly, there are E\mathbf{E} eastern stations connected through E1\mathbf{E}-1 connections such that there is exactly one path between any two distinct eastern stations. After the overpass connection is built connecting one western and one eastern station, there will be exactly one path between any two distinct stations.

A complete map is a map that has W+E1\mathbf{W}+\mathbf{E}-1 total connections and exactly one path between any pair of stations. The average distance of a complete map is the average of the length of paths between all pairs of different stations. The length of a path is one less than the length of the list of stations that defines it (e.g., the path between directly connected stations has a length of 1).

As an example, the picture below illustrates a scenario with W=2\mathbf{W}=2 stations on the west side and E=3\mathbf{E}=3 stations on the east side. There are 2 possible overpasses shown.

This table shows the lengths of the paths between pairs of stations if each overpass were to be built.

West 1 West 2 1 ↔ 1 2 ↔ 3
West 1 East 1 1 3
East 2 3
East 3 2 2
West 2 East 1
East 2 4
East 3 3 1
East 1 East 2 2
East 3 1
East 2
Average: 2 1.8

Given the current stations and connections, and a list of options for the overpass connection, help Ekiya by calculating the average distance of the map that would result if that option was the only overpass connection built.

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} test cases follow. Each test case starts with a line with three integers W\mathbf{W}, E\mathbf{E}, and C\mathbf{C}, the number of western and eastern stations, and the number of options for the overpass connection, respectively. Western stations are numbered between 11 and W\mathbf{W} and eastern connections are numbered between 11 and E\mathbf{E}.

The second line of a test case contains W1\mathbf{W}-1 integers X1\mathbf{X}_1, X2\mathbf{X}_2, \ldots, XW1\mathbf{X}_{\mathbf{W}-1} representing that the ii-th existing connection among western stations connects western stations ii and Xi\mathbf{X}_i.

The third line of a test case contains E1\mathbf{E}-1 integers F1\mathbf{F}_1, F2\mathbf{F}_2, \ldots, FE1\mathbf{F}_{\mathbf{E}-1} representing that the jj-th existing connection among eastern stations connects eastern stations jj and Fj\mathbf{F}_j.

Finally, the last C\mathbf{C} lines of a test case describe the options for the overpass connection. The kk-th of these lines contains two integers Ak\mathbf{A}_k and Bk\mathbf{B}_k representing the western and eastern stations, respectively, that the kk-th option for an overpass connection would connect.

输出格式

For each test case, output one line containing Case #x: y1y_1 y2y_2 \cdots yCy_{\mathbf{C}}, where xx is the test case number (starting from 11) and yky_k is the average distance of the map resulting in adding the kk-th option as an overpass connection to all existing connections.

y1y_1, y2y_2, \ldots and yky_k will be considered correct if they are within an absolute or relative error of 10610^{-6} of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

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

提示

Sample Explanation

Sample Case #1 is explained and illustrated in the problem statement. Sample Case #2 and Sample Case #3 are illustrated below.

Limits

  • 1T1001 \leq \mathbf{T} \leq 100.
  • 2W1052 \leq \mathbf{W} \leq 10^{5}.
  • 2E1052 \leq \mathbf{E} \leq 10^{5}.
  • i+1XiWi+1 \leq \mathbf{X}_{i} \leq \mathbf{W}, for all ii. (This implies that there is exactly one path between each pair of western stations.)
  • j+1FjEj+1 \leq \mathbf{F}_{j} \leq \mathbf{E}, for all jj. (This implies that there is exactly one path between each pair of eastern stations.)
  • 1AkW1 \leq \mathbf{A}_{k} \leq \mathbf{W}, for all kk.
  • 1BkE1 \leq \mathbf{B}_{k} \leq \mathbf{E}, for all kk.
  • $(\mathbf{A}_{k}, \mathbf{B}_{k}) \neq (\mathbf{A}_{\ell}, \mathbf{B}_{\ell})$, for all kk \neq \ell. (Each listed overpass connection is different.)

Test Set 1 (5 Pts, Visible Verdict)

  • Time limit: 20 seconds.
  • 1C21 \leq \mathbf{C} \leq 2.

Test Set 2 (7 Pts, Hidden Verdict)

  • Time limit: 40 seconds.
  • 1C1051 \leq \mathbf{C} \leq 10^{5}.