1 /* 2 题目大意：有n个房间由n-1个隧道连接起来，从1号房间开始， 3 每个节点i都有三种可能： 4 1.被杀死，回到节点1，概率为ki; 5 2.找到出口，离开迷宫，概率ei; 6 3.与它相连的有m个房间，到任意相连房间的概率(1-ki-ei)/m; 7 求走出迷宫要走房间个数的期望。 8 E[i]表示在节点i处的期望值，E[1]即为答案,从后往前推。 9 E[1]=k1*E[1]+sigma(E[j])*(1-k1-e1)/childsize[i]+(1-k1-e1)10 非叶子节点：11 E[i]=ki*E[1]+(E[father[i]]+sigma(E[j])*(1-ki-ei)/(childsize[i]+1)+(1-ki-ei)12 叶子节点：13 E[i]=ki*E[1]+E[father[i]]*(1-ki-ei)+(1-ki-ei)14 一般形式：15 E[i]=Ai*E[1]+Bi*E[father[i]]*(1-ki-ei)+Ci;16 E[j]=Aj*E[1]+Bj*E[father[j]]*(1-kj-ej)+Cj17 把儿子节点代入18 E[i]=(Ai+(1-ki-ei)/m*sigma(Aj))*E[1]+Bi*E[father[i]]+E[i]*(1-ki-ei)/m*sigma(B[j])+(1-ki-ei)/m*sigma(Cj)+(1-ki-ei)19 把E[i]化简，从下递推到上，可求出E[1]=A1*E[1]+B1*0+C1。20 */21 #pragma warning (disable : 4786)22 #include <iostream>23 #include <cstdio>24 #include <cstring>25 #include <cmath>26 #include <vector>27 using namespace std;28 29 const double eps=1e-10;30 const int maxn=10005;31 double E[maxn],A[maxn],B[maxn],C[maxn];32 double k[maxn],e[maxn];33 vector<int> f[maxn];34 35 bool dfs(int v,int pre)36 {37     A[v]=k[v];B[v]=(1-k[v]-e[v])/f[v].size();38     C[v]=1-k[v]-e[v];39     double temp=0;40     for(int i=0;i<f[v].size();i++)41     {42         int u=f[v][i];43         if(u==pre) continue;44         if(!dfs(u,v)) return false;45         A[v]+=B[v]*A[u];46         C[v]+=B[v]*C[u];47         temp+=B[v]*B[u] ;48     }49     if(fabs(temp-1)<eps)50         return false;51     A[v]/=(1-temp);52     B[v]/=(1-temp);53     C[v]/=(1-temp);54     return true;55 }56 int main()57 {58     int t,n,i,a,b,icase=0;59     scanf("%d",&t);60     while(t--)61     {62         scanf("%d",&n);63         for(i=1;i<=n;i++)  f[i].clear();64         for(i=1;i<n;i++)65         {66             scanf("%d%d",&a,&b);67             f[a].push_back(b);68             f[b].push_back(a);69         }70         for(i=1;i<=n;i++)71         {72             scanf("%lf%lf",&k[i],&e[i]);73             k[i]/=100;e[i]/=100;74         }75         printf("Case %d: ",++icase);76         if(dfs(1,-1) && fabs(1-A[1])>eps)77             printf("%.6lf\n",C[1]/(1-A[1]));78         else printf("impossible\n");79     }80     return 0;81 }