2015
05-23

# 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

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

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

http://acm.hdu.edu.cn/showproblem.php?pid=4219

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

#define SZ(v) ((int)(v).size())
const int MAXN = 65, MAXS = 520;

int t, n, l, s, a, b;
vector<int> maps[MAXN];
double dp[MAXN][MAXS], son[MAXS], tmp[MAXS], ans, e;

void dfs(int x, int p)
{
for (int i = 0; i <= s; ++ i)
dp[x][i] = 0.0;
dp[x][0] = 1.0;
for (int i = 0; i < SZ(maps[x]); ++ i)
{
int c = maps[x][i];
if (c != p)
{
dfs(c, x);
for (int j = 0; j <= s; ++ j)
son[j] = tmp[j] = 0.0;

for (int j = 0; j <= l; ++ j)
for (int k = 0; k <= s; ++ k)
if (j + k <= s)
son[j + k] += dp[c][k] * e;

/*  for(int i=0;i<=s;i++)
cout<< son[i] <<" ";
cout<<endl;
for(int i=0;i<=s;i++)
cout<< dp[x][i] <<" ";
cout<<endl;
cout<<endl;*/
for (int j = 0; j <= s; ++ j)
{
//cout<<s-j<<" :: ";
for (int k = 0; k <= s - j; ++ k)
{
//cout<<max(i,j)<<endl;
tmp[max(j, k)] += son[j] * dp[x][k];
// cout<< max(j,k)<<" "<<tmp[max(j,k)]<<endl;
}
}
for (int j = 0; j <= s; ++ j)
dp[x][j] = tmp[j];
// cout<<endl;
}
}
}

int main()
{
scanf("%d", &t);
for (int m = 1; m <= t; ++ m)
{
scanf("%d%d%d", &n, &l, &s);
e = 1 / (l + 1.0);
for (int i = 1; i <= n; ++ i)
maps[i].clear();
for (int i = 1; i < n; ++ i)
{
scanf("%d%d", &a, &b);
maps[a].push_back(b);
maps[b].push_back(a);
}
dfs(1, -1);
ans = 0.0;
/*for(int i=1;i<=n;i++)
{
for(int j=0;j<=s;j++)
printf("%.3lf ",dp[i][j]);
cout<<endl;
}*/
for (int i = 0; i <= s; ++ i)
ans += dp[1][i];
printf("Case %d: %.6lf\n", m, ans);
}
return 0;
}