对于叶子节点和非叶子节点非别列公式。
然后化简公式。
和非树上的差不多。。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
#define eps 1e-9
#define zero(x) ((fabs(x)<eps?0:x))
#define maxn 11000
#define pb push_back
double a[maxn],b[maxn],c[maxn];
double k[maxn],e[maxn],p[maxn];
vector<int>vec[maxn];
int dfs(int x,int pre)
{int m=vec[x].size();double pp=1.0*p[x]/m;a[x]=k[x];b[x]=pp;c[x]=p[x];double tmp;tmp=1.0;for(int i=0;i<m;i++){int y=vec[x][i];if(y==pre)continue;if(!dfs(y,x))return false;a[x]+=pp*a[y];c[x]+=pp*c[y];tmp-=pp*b[y];}if(fabs(tmp)<eps)return false;a[x]=a[x]/tmp;b[x]=b[x]/tmp;c[x]=c[x]/tmp;return true;
}
int main()
{int T,cas;cas=0;scanf("%d",&T);while(T--){cas++;int n,x,y;scanf("%d",&n);for(int i=1;i<=n;i++)vec[i].clear();for(int i=1;i<n;i++){scanf("%d%d",&x,&y);vec[x].pb(y);vec[y].pb(x);}for(int i=1;i<=n;i++){scanf("%lf%lf",&k[i],&e[i]);k[i]=k[i]/100.0;e[i]=e[i]/100.0;p[i]=1-k[i]-e[i];}printf("Case %d: ",cas);if(dfs(1,-1)&&fabs(a[1]-1)>eps){printf("%.6lf\n",c[1]/(1-a[1]));}else{puts("impossible");}}return 0;
}