本题目的状态转移表达式是很好写的，但一个节点不仅依赖子节点，还会依赖父亲节点和1好节点的期望值。
假定 p = (1-ei-ki)/m ，（其中m为i节点的子节点和父亲节点总个数的和）
Ei = ki * E1 + ei*0 + p*( Ef + 1) + p* ∑（Ej + 1） （ 其中j为i的某一个子节点，f为i的父亲节点） ...........................(1)
设定Ei = Ai*E1 + Bi*Ef + Ci;.....................................(2)
那么对于Ｅj 也有同样的设定Ej = Aj*E1 + Bj*Ef + Cj;................................(3)
可以将(3）带入(1）整理成(2) 的形式，进而求出Ai,Bi,Ci.这样就可以用递归算法求解了。
@H_301_17@//#pragma comment(linker,"/STACK:1024000000,1024000000") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> #include <list> #include <cstdlib> #include <queue> #include <stack> #include <cmath> #define ALL(a) a.begin(),a.end() #define clr(a,x) memset(a,x,sizeof a) #define fst first #define snd second #define pb push_back #define lowbit(x) (x&(-x)) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define rep1(i,y) for(int i=x;i<=y;i++) #define rep(i,n) for(int i=0;i<(int)n;i++) using namespace std; const double eps = 1e-10; typedef long long LL; typedef long long ll; typedef pair<int,int> pii; const int inf =0x3f3f3f3f; inline int zero(double te){ return fabs(te)<eps; } const int N = 10101; vector<int> G[N]; double k[N],e[N],E[N],A[N],B[N],C[N]; bool dfs(int u,int f){ double p = (1.0-k[u]-e[u])/G[u].size(); double fenm = 1; if(G[u].size()==1 && G[u][0]==f){ A[u] = k[u],B[u]=1-k[u]-e[u],C[u]=1-k[u]-e[u]; return true; } A[u] = k[u],B[u] =(p),C[u]=(u==1 ? 0 : p); for(int i=0;i<G[u].size();i++){ int v = G[u][i]; if(v == f) continue; if(!dfs(v,u)) return false; fenm-=p*B[v]; A[u]+=p*A[v]; C[u]+=p*(C[v]+1); } if(zero(fenm)) return false; A[u]/=fenm; B[u]/=fenm; C[u]/=fenm; return true; } int n,d; int main() { int T,kase=1; scanf("%d",&T); while(T--){ scanf("%d",&n); rep1(i,1,n) G[i].clear(); rep1(i,n-1){ int x,y; scanf("%d %d",&x,&y); G[x].push_back(y); G[y].push_back(x); } rep1(i,n) { scanf("%lf %lf",&k[i],&e[i]); k[i]/=100; e[i]/=100; } if(dfs(1,-1) && !zero(1-A[1])){ double res =C[1]/(1-A[1]); printf("Case %d: %.6lf\n",kase++,res); } else printf("Case %d: impossible\n",kase++); } return 0; } 原文链接：https://www.f2er.com/javaschema/284470.html