题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4035
题目意思：
有n个房间，有n-1条通道连接这n个房间（每两个房间之间有且只有一条路，所以实际上就是一棵树），在每个房间中，有三种选择要么被杀则回到第一个房间，概率为ki,要么从出口逃离概率为ei,要么通过通道到达其他的房间。
解题思路：
好题。
状态转移方程很好想，但是求的时候有技巧，不能直接用高斯消元来求（n有10000）肯定会超时。发现知，此题是在一棵树上转移，所以可以借助树的特点，分成两部分儿子和父亲，抽象出系数，然后从叶子节点向上求出父亲节点。
以下文字选自http://blog.csdn.net/morgan_xww/article/details/6776947
设 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;
由此可得
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则无解...
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#define eps 1e-9
#define INF 0x3fffffff
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std; #define Maxn 10100 int deg[Maxn],cnt,n;
double A[Maxn],B[Maxn],C[Maxn]; //分别表示系数
double k[Maxn],e[Maxn];//表示被杀和逃离概率 struct Edge
{
int v;
struct Edge * next;
}edge[Maxn<<1],*head[Maxn<<1]; void add(int a,int b)
{
++cnt;
deg[a]++; //度数
edge[cnt].v=b,edge[cnt].next=head[a];
head[a]=&edge[cnt];
}
void dfs(int cur,int pre)
{
struct Edge * p=head[cur];
bool flag=true;
double suma=0,sumb=0,sumc=0; while(p)
{
int v=p->v;
if(v!=pre)
{
flag=false; //不是叶子节点
dfs(v,cur);suma+=A[v];sumb+=B[v];sumc+=C[v];
} //求出儿子节点的各和
p=p->next;
}
if(flag) //叶子节点
{
double t=1-k[cur]-e[cur];
A[cur]=k[cur],B[cur]=t,C[cur]=t;
return ;
}//非叶子节点
double temp=(1-k[cur]-e[cur])/deg[cur];
double tt=1-temp*sumb; A[cur]=(k[cur]+temp*suma)/tt;
B[cur]=temp/tt;
C[cur]=(temp*sumc+(1-k[cur]-e[cur]))/tt;
return ;
} int main()
{
int t; scanf("%d",&t);
for(int ca=1;ca<=t;ca++)
{
scanf("%d",&n);
memset(head,NULL,sizeof(head));
memset(deg,0,sizeof(deg));
cnt=0; for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
for(int i=1;i<=n;i++)
{
double a,b;
scanf("%lf%lf",&a,&b);
k[i]=a/100.0,e[i]=b/100.0;
}
dfs(1,-1);
printf("Case %d: ",ca);
if(fabs(1-A[1])<eps) //这里卡精度
printf("impossible\n");
else
printf("%.5f\n",C[1]/(1.0-A[1]));
}
return 0;
}