Maze
http://acm.hdu.edu.cn/showproblem.php?pid=4035
?
分析：
在樹上走來走去，然后在一個點可以k的概率回到1，可以e的概率走出去，可以1-k-e的概率走到其他的位置（分為父節點和子節點討論）。
轉移方程就是：$dp[i] = dp[1] \times k + 0 \times e + \frac{1 - k - e}{deg[i]} \times (dp[fa]+1) + \sum\limits_{j∈child[i]}\frac{1 - k - e}{deg[i]} \times (dp[j]+1)$
發現式子沒法轉換，有后效性，然后式子只與$dp[1],dp[fa],dp[child[i]]$有關系，可以寫成統一的格式：$dp[i] = A_i \times dp[1] +B_i \times dp[fa] +C_i$
這樣寫完了，發現$A,B,C$就可以從它的子節點轉移了，然后可以從葉子節點推到根。最后$dp[1] = \frac{C[1]}{1-A[1]}$。
https://www.cnblogs.com/kuangbin/archive/2012/10/03/2711108.html
?
代碼：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<cctype> 7 #include<set> 8 #include<vector> 9 #include<queue> 10 #include<map> 11 using namespace std; 12 typedef long long LL; 13 14 inline int read() { 15 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; 16 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; 17 } 18 19 const int N = 10010; 20 const double eps = 1e-10; 21 22 double A[N], B[N], C[N], k[N], e[N]; 23 vector<int> T[N]; 24 25 bool dfs(int u,int fa) { 26 double m = 1.0 * T[u].size(); 27 A[u] = k[u], B[u] = (1 - k[u] - e[u]) / m, C[u] = 1 - k[u] - e[u]; 28 double t = 0; 29 for (int i=0; i<m; ++i) { 30 int v = T[u][i]; 31 if (v == fa) continue; 32 if (!dfs(v, u)) return false; 33 A[u] += (1 - k[u] - e[u]) / m * A[v]; 34 C[u] += (1 - k[u] - e[u]) / m * C[v]; 35 t += (1 - k[u] - e[u]) / m * B[v]; 36 } 37 if (fabs(1 - t) <= eps) return false; 38 A[u] /= (1 - t), B[u] /= (1 - t), C[u] /= (1 - t); 39 return true; 40 } 41 42 int main() { 43 for (int Case=read(),t=1; t<=Case; ++t) { 44 int n = read(); 45 for (int i=1; i<=n; ++i) T[i].clear(); 46 for (int i=1; i<n; ++i) { 47 int u = read(), v = read(); 48 T[u].push_back(v), T[v].push_back(u); 49 } 50 for (int i=1; i<=n; ++i) { 51 int a = read(), v = read(); 52 k[i] = (double)a / 100.0; 53 e[i] = (double)v / 100.0; 54 } 55 printf("Case %d: ",t); 56 if (dfs(1, 0) && fabs(A[1] - 1) > eps) 57 printf("%.10lf\n",C[1] / (1 - A[1])); 58 else puts("impossible"); 59 } 60 return 0; 61 }
?
)
