【題解】：這是一道樹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