题意：
给你n个节点的树，从1节点开始走，到每个节点都有三种情况，被杀死回到1节点，找到隐藏的出口出去，沿着当前节点相邻的边走到下一个节点，给出每个节点三种情况发生的概率分别为ki,ei,1-ki-ei，求找到出口时已经过的边数的期望。
分析：
用树状dp考虑问题。当节点是叶子节点时它只是向父节点走，非叶子节点可以向父亲节点和所有孩子节点走。
Ei表示到i节点经过边数的期望
则叶子节点：Ei=ki*E1+(1-ki-ei)*(E[par[i]]+1);//par[i]表示i的父亲节点
非叶子节点：Ei=ki*E1+(1-ki-ei)*(E[par[i]]/m+Σ(E[son[i]])/m+1)//m表示与i节点相连的边数,son[i]表示i节点孩子
接下来就是处理环了
令 Ei=ai*E1+bi*E[par[i]]+ci;//关键
叶子节点：ai=ki,bi=1-ki-ei,ci=1-ki-ei
非叶子节点：设j是i的孩子Σ(E[son[i]]=Σ(E[j])=Σai*E1+Σbi*Ei+Σci代入得
令 tmp=(1-ki-ei)*Σbi/m;
ai=(ki+(1-ki-ei)*Σai/m)/(1-tmp)
bi=(1-ki-ei)/(1-tmp)/m;
ci=((1-ki-ei)*Σci/m+1-ki-ei)/(1-tmp);
则E1=a1*E1+bi*0+ci可得答案，当tmp趋于1时无解
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define exp 1e-9
#define All 1,N,1
#define N 10010
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
int used[N],f,n;
double e[N],k[N],a[N],b[N],c[N];
vector<int>t[N];
void dfs(int u){
if(f)return;
used[u]=;
int num=t[u].size();
a[u]=k[u];
b[u]=(-k[u]-e[u])/num;
c[u]=-k[u]-e[u];
double tmp=;
for(int i=;i<num;++i){
int v=t[u][i];
if(used[v])continue;
dfs(v);
a[u]+=(-k[u]-e[u])/num*a[v];
tmp+=(-k[u]-e[u])/num*b[v];
c[u]+=(-k[u]-e[u])/num*c[v];
}
if(fabs(-tmp)<exp){
f=;
return;
}
a[u]/=(-tmp);
b[u]/=(-tmp);
c[u]/=(-tmp);
}
int main()
{
int test,cas=;
scanf("%d",&test);
while(test--){
scanf("%d",&n);
for(int i=;i<=n;++i)
t[i].clear();
int st,ed;
for(int i=;i<n-;++i){
scanf("%d%d",&st,&ed);
t[st].push_back(ed);
t[ed].push_back(st);
}
int kk,ee;
for(int i=;i<=n;++i){
scanf("%d%d",&kk,&ee);
k[i]=kk/100.0;
e[i]=ee/100.0;
}
memset(used,,sizeof(used));
f=;
dfs();
printf("Case %d: ",++cas);
if(!f&&(1.0-a[])>exp){
printf("%lf\n",c[]/(-a[]));
}
else{
printf("impossible\n");
}
}
return ;
}