亟隐

朝不闻道,夕亦死可矣

07/26
22:41
DP 算法区

HDU 4219 Randomization?

地址:戳这里

Problem 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.

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 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
Output
For each test case, output the case number first, then the probability rounded to six fractional digits.
Sample 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 Output
Case 1: 0.750000 Case 2: 0.500000 Case 3: 0.624832
Author
iSea@WHU

当成有跟树,如果全部节点下最远路径不超过s,并且没有两个子树下最远点到此节点和大于s,树上就不存在一条大于s的路径。用f[i][j]表示符合上面情况下i节点到其后代最远距离为j的概率。考虑有两颗子树,分别为x和y,到达i的最远距离分别在g[x][j]和g[y][j]。如果最远距离来自x子树,那么f[i][j]=g[x][j]*g[y][k],其中k在区间[0,min(s-j,j)]之间,这里可以用个前缀和统计。同理考虑最远距离为y子树的情况,然后减去重复计算的地方f[i][j]-=g[x][j]*g[y][j](j*2<=s)。多子树的时候只需要记录之前子树更新的f[i]和新子树合并的情况,f[i]可以代替上面的g[x],合并后再更新f[i]。

代码:戳这里