【题意】：给定一棵树，给定边权的区间[0,L]，求最终树的最长路<=S的概率； 

【题解】：武大校赛的树dp，放了好久，看着题解勉强过了。只可以说我的树dp太水了，还停留在背包的阶段。
              设状态dp[i][j]表示以i为根的子树，其叶子结点到i的最长距离为j且该子树最长路径不超过s的概率。
              对于u的一个子树v，先枚举u连v的长度，然后再把之前的子树和v这条链合并，好复杂，不会表达了，直接研究代码吧。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 70
22 #define maxs 530
23 int n, l, s;
24 double dp[maxn][maxs];
25 double son[maxs], tmp[maxs];
26 double e;
27 vector<int> vec[maxn];
28 void dfs(int u, int fa) {
29     memset(dp[u], 0, sizeof(dp[u]));
30     dp[u][0] = 1.0;
31     int size = vec[u].size();
32     for(int i = 0; i < size; i++) {
33         int v = vec[u][i];
34         if(v == fa) continue;
35         dfs(v, u);
36         memset(son, 0, sizeof(son));
37         memset(tmp, 0, sizeof(tmp));
38         for(int j = 0; j <= l; j++)
39             for(int k = 0; k <= s; k++)
40                 if(j + k <= s)
41                     son[j+k] += e * dp[v][k];
42         for(int j = 0; j <= s; j++)
43             for(int k = 0; k <= s - j; k++)
44                 tmp[max(j, k)] += son[j] * dp[u][k];
45         for(int j = 0; j <= s; j++)
46             dp[u][j] = tmp[j];
47     }
48 }
49 
50 int main() {
51     int T, Case = 1;
52     scanf("%d", &T);
53     while(T--) {
54         scanf("%d%d%d", &n, &l, &s);
55         for(int i = 0; i <= n; i++) vec[i].clear();
56         e = 1.0 / (1.0 + l);
57         for(int i = 1; i < n; i++) {
58             int a, b;
59             scanf("%d%d", &a, &b);
60             vec[a].pb(b);
61             vec[b].pb(a);
62         }
63         dfs(1, -1);
64         double ans = 0.0;
65         for(int i = 0; i <= s; i++) ans += dp[1][i];
66         printf("Case %d: %.6f\n", Case++, ans);
67     }
68     return 0;
69 }
70