题意：
有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树，
从结点1出发，开始走，在每个结点i都有3种可能：
1.被杀死，回到结点1处（概率为ki）
2.找到出口，走出迷宫 （概率为ei）
3.和该点相连有m条边，随机走一条
求：走出迷宫所要走的边数的期望值。
思路：
设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。
叶子结点：有3种情况：kill ；exit（成功出去的期望为0） ；回到父节点。
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;
由此可得
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);
若 A1趋近于1则无解...
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4035
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 10005
using namespace std;
vector<int>p[MAX];
double A[MAX],B[MAX],C[MAX],k[MAX],e[MAX];
bool dfs(int n,int f)
{
int m=p[n].size();
double d=-k[n]-e[n];
A[n]=k[n];
B[n]=d/m;
C[n]=d;
if(m==&&f!=-) return true;
double temp=0.0;
for(int i=;i<m;i++){
int v=p[n][i];
if(v==f) continue;
if(!dfs(v,n)) return false;
A[n]+=B[n]*A[v];
C[n]+=B[n]*C[v];
temp+=B[n]*B[v];
}
temp=-temp;
if(temp<=1e-) return false;
A[n]/=temp;
B[n]/=temp;
C[n]/=temp;
return true;
}
int main(){
int t,i,n,a,b,c=;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=;i<=n;i++) p[i].clear();
for(i=;i<n;i++){
scanf("%d%d",&a,&b);
p[a].push_back(b);
p[b].push_back(a);
}
for(i=;i<=n;i++){
scanf("%lf%lf",&k[i],&e[i]);
k[i]/=100.0;
e[i]/=100.0;
}
printf("Case %d: ",++c);
if(dfs(,-)&&fabs(-A[])>1e-)
printf("%.6lf\n",C[]/(-A[]));
else printf("impossible\n");
}
return ;
}