Randomization?

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.

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 Ai and Bi, describing an edge of the tree.

Technical Specification
1. 1 <= T <= 512
2. 1 <= N <= 64
3. 1 <= L <= 8, 1 <= S <= 512
4. 1 <= Ai, Bi <= N

For each test case, output the case number first, then the probability rounded to six fractional digits.

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

Case 1: 0.750000
Case 2: 0.500000
Case 3: 0.624832

iSea@WHU

首届华中区程序设计邀请赛暨第十届武汉大学程序设计大赛