测试地址：Maze
题目大意：有一个树形的迷宫，有N个房间（标号为1~N）以及N-1条通道将它们连通，一开始在1号房间，每进入一个房间i，有k[i]的概率被陷阱杀死回到房间1，有e[i]的概率找到出口逃离迷宫，如果没有找到出口也没有被杀，那么就在与该房间相连的通道中等概率随机选一条走，求逃离迷宫所需要走的通道数的期望值（如果不能逃离输出impossible）。
做法：求期望采用逆推的方式。设f[i]表示从房间i开始走，逃离迷宫所需要走的通道数的期望值，令fa[i]为点i的父亲（整棵树以1为根时），deg[i]为点i的度数，我们知道对于每个叶子节点有：f[i]=k[i]*f[1]+(1-k[i]-e[i])*(f[fa[i]]+1)，对于每个节点有：f[i]=k[i]*f[1]+(1-k[i]-e[i])/deg[i]*Σ(f[j]+1)，其中j满足点i和点j之间有直接连边。我们可以发现，一个节点的期望值跟三个部分有关：点1的期望，父亲节点的期望，儿子节点的期望，而儿子节点的期望也和这三个部分有关，一直下到叶子节点，因为叶子节点没有儿子节点，所以我们可以把叶子节点作为突破口。我们可以将每个点的期望表示成这样一个式子：f[i]=x*f[1]+y*f[fa[i]]+z，显然对于叶子节点有：x=k[i],y=1-k[i]-e[i],z=1-k[i]-e[i]。然后对于其他节点，因为其儿子节点的父亲节点就是它本身，所以我们可以用待定系数法求出这个节点的期望式。在最后，我们可以求出f[1]的期望式，即f[1]=x*f[1]+y*f[fa[1]]+z，由于fa[1]没有意义，我们把它舍去，变化一下式子就可以得到：f[1]=z/(1-x)，这就是我们要求的答案了。注意当x无限趋近于1时（|x-1|≤1e-9），f[1]无法解出，这时就输出impossible就可以了。
以下是本人代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define eps 1e-9
using namespace std;
int T,n,first[10010],tot,fa[10010];
double f1[10010],f2[10010],f3[10010],k[10010],e[10010]; //f1,f2,f3即上文提到的系数x,y,z
struct edge {int v,next;} E[20010];
bool flag;
void insert(int a,int b)
{
E[++tot].v=b,E[tot].next=first[a],first[a]=tot;
}
void treedp(int v)
{
double s=1,a;
f1[v]=f2[v]=f3[v]=0;
for(int i=first[v];i;i=E[i].next)
if (E[i].v!=fa[v])
{
fa[E[i].v]=v;
treedp(E[i].v);
f1[v]+=f1[E[i].v];
f2[v]+=f2[E[i].v];
f3[v]+=f3[E[i].v];
s+=1.0;
}
if (v==1) s-=1.0;
f1[v]=f1[v]*(1-k[v]-e[v])/s;
f2[v]=f2[v]*(1-k[v]-e[v])/s;
f3[v]=f3[v]*(1-k[v]-e[v])/s;
a=1-f2[v];
f1[v]+=k[v];
f2[v]=(1-k[v]-e[v])/s;
f3[v]+=(1-k[v]-e[v]);
f1[v]/=a,f2[v]/=a,f3[v]/=a;
}
int main()
{
scanf("%d",&T);
for(int t=1;t<=T;t++)
{
scanf("%d",&n);
memset(first,0,sizeof(first));
tot=0;
for(int i=1,a,b;i<n;i++)
{
scanf("%d%d",&a,&b);
insert(a,b),insert(b,a);
}
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&k[i],&e[i]);
k[i]/=100.0,e[i]/=100.0;
}
fa[1]=0;
treedp(1);
if (fabs(f1[1]-1)<=eps) printf("Case %d: impossible
",t);
else printf("Case %d: %.6lf
",t,f3[1]/(1-f1[1]));
}
return 0;
}