8982: HDU4219 - Randomization?
[Creator : ]
Description
Random is the real life. What we see and sense everyday are absolutely randomly happened. Randomization is the process of making something random, as the nature.
Given a tree with $N$ nodes, to be more precisely, a tree is a graph in which each pair of nodes has and only has one path. All of the edges’ length is a random integer lies in interval [0, L] with equal probability. iSea want to know the probability to form a tree, whose edges’ length are randomly generated in the given interval, and in which the path's length of every two nodes does not exceed S.
Given a tree with $N$ nodes, to be more precisely, a tree is a graph in which each pair of nodes has and only has one path. All of the edges’ length is a random integer lies in interval [0, L] with equal probability. iSea want to know the probability to form a tree, whose edges’ length are randomly generated in the given interval, and in which the path's length of every two nodes does not exceed S.
Input
The first line contains a single integer $T$, indicating the number of test cases.
Each test case includes three integers $N, L, S$.
Then $N - 1$ lines following, each line contains two integers $A_i$ and $B_i$, describing an edge of the tree.
Each test case includes three integers $N, L, S$.
Then $N - 1$ lines following, each line contains two integers $A_i$ and $B_i$, describing an edge of the tree.
Output
For each test case, output the case number first, then the probability rounded to six fractional digits.
Constraints
$1 \leq T \leq 512$
$1 \leq N \leq 64$
$1 \leq L \leq 8,\ 1 \leq S \leq 512$
$1 \leq A_i, B_i \leq N$
$1 \leq N \leq 64$
$1 \leq L \leq 8,\ 1 \leq S \leq 512$
$1 \leq A_i, B_i \leq N$
Sample 1 Input
3
2 3 2
1 2
4 3 4
1 2
2 3
3 4
7 4 10
1 2
2 3
4 5
2 6
4 7
4 6
Sample 1 Output
Case 1: 0.750000
Case 2: 0.500000
Case 3: 0.624832