【题解】：这是一道树dp求期望的题目。
设E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。
叶子结点：
E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);
= ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei);
非叶子结点：（m为与结点相连的边数）
E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) );
= ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei);
设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;
对于非叶子结点i，设j为i的孩子结点，则
∑(E[child[i]]) = ∑E[j]
= ∑(Aj*E[1] + Bj*E[father[j]] + Cj)
= ∑(Aj*E[1] + Bj*E[i] + Cj)
代入上面的式子得
(1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj;
由此可得
对于非叶子结点，其中j为i的儿子结点
Ai = (ki+(1 - ki - ei) / m * ∑Aj) / (1 - (1 - ki - ei) / m * ∑Bj);
Bi = (1 - ki - ei) / m / (1 - (1 - ki - ei) / m * ∑Bj);
Ci = ((1 - ki - ei) + (1 - ki - ei) / m * ∑Cj) / (1 - (1 - ki - ei) / m * ∑Bj);
对于叶子结点
Ai = ki;
Bi = 1 - ki - ei;
Ci = 1 - ki - ei;
从叶子结点开始，直到算出 A1,B1,C1;
因为 E[1] = A1 * E[1] + B1 * 0 + C1;
所以 E[1] = C1 / (1 - A1). 当(1 - A[1]) 趋近于0时，E[1] 趋近于∞，因此无解。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "vector"
5 #include "cmath"
6 using namespace std;
7 #define pb push_back
8 #define maxn 10050
9 #define eps 1e-10
10 vector<int> g[maxn];
11 double k[maxn], e[maxn], p[maxn];
12 double a[maxn], b[maxn], c[maxn];
13 int n;
14
15 void dfs(int u, int fa) {
16 int size = g[u].size();
17 if(size == 1 && fa != -1) {
18 a[u] = k[u];
19 b[u] = c[u] = p[u];
20 return;
21 }
22 double aa = 0, bb = 0, cc = 0;
23 for(int i = 0; i < size; i++) {
24 int v = g[u][i];
25 if(v == fa) continue;
26 dfs(v, u);
27 aa += a[v], bb += b[v], cc += c[v];
28 }
29 double tmp = (1 - p[u] * bb / size);
30 a[u] = (k[u] + p[u] * aa / size) / tmp;
31 b[u] = (p[u] / size) / tmp;
32 c[u] = (p[u] + p[u] * cc / size) / tmp;
33 return;
34 }
35
36
37 int main() {
38 int T, Case = 1;
39 int u, v;
40 scanf("%d", &T);
41 while(T--) {
42 scanf("%d", &n);
43 for(int i = 0; i < maxn; i++) g[i].clear();
44 for(int i = 0; i < n - 1; i++) {
45 scanf("%d%d:", &u, &v);
46 g[u].pb(v);
47 g[v].pb(u);
48 }
49 for(int i = 1; i <= n; i++) {
50 scanf("%lf%lf", &k[i], &e[i]);
51 k[i] /= 100, e[i] /= 100;
52 p[i] = 1 - k[i] - e[i];
53 }
54 dfs(1, -1);
55 printf("Case %d: ", Case++);
56 if(fabs(1 - a[1]) < eps) printf("impossible\n");
57 else {
58 double ans = c[1] / (1 - a[1]);
59 printf("%.6f\n", ans);
60 }
61 }
62 return 0;
63 }
64