1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 using namespace std; 5 #define N 10005 6 #define del 1e-10 7 vector <int> G[N]; 8 double A[N],B[N],C[N],k[N],e[N],p[N]; 9 int n;10 bool solve(int u,int fa)11 {12     A[u] = k[u];13     B[u] = p[u] / G[u].size();14     C[u] = p[u];15 16     if(G[u].size() == 1 && fa!=0)17         return true;18 19     double tmp = 0;20     for(int i=0;i<G[u].size();i++){21         int j = G[u][i];22         if(j!=fa)23         {24             //既是一个判断过程也是一个找叶子节点的过程，先做递归是为了先更新好叶子节点作为底层的信息，25             //用以推得上层信息26             if(!solve(j,u))27                 return false;28             A[u]+=B[u]*A[j];29             C[u]+=B[u]*C[j];30             tmp +=B[u]*B[j];31         }32     }33 34     tmp = 1-tmp;35     if(tmp < del)36         return false;37 38     A[u] /= tmp;39     B[u] /= tmp;40     C[u] /= tmp;41 42     return true;43 }44 45 int main()46 {47     int T,a,b,c,d;48     scanf("%d",&T);49     for(int kase=1;kase<=T;kase++){50         scanf("%d",&n);51 52         for(int i=1;i<=n;i++)53             G[i].clear();54 55         for(int i=1;i<n;i++){56             scanf("%d%d",&a,&b);57             G[a].push_back(b);58             G[b].push_back(a);59         }60         for(int i=1;i<=n;i++){61             scanf("%d%d",&c,&d);62             k[i] = c*1.0/100;63             e[i] = d*1.0/100;64             p[i] = 1-k[i]-e[i];65         }66 67         printf("Case %d: ",kase);68 69         if(!solve(1,0) || 1-A[1]<del){70             printf("impossible\n");71             continue;72         }73 74         printf("%.6f\n",C[1] / (1-A[1]));75     }76 }