Aimee

打着期望dp的名字推式子

这位大佬写的非常好

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int t;        
int to[10001];
int x,y;
int n;
int head[40000];
int p;   
struct e{
    int ne;
    int to;
} ed[100001];
double Ai[100001],Ar[100001];
double a[100001],b[100001],c[100001];
double xz=1e-9;
void add(int f,int t){
    p++;
    ed[p].ne=head[f];
    ed[p].to=t;
    head[f]=p;
}
bool dfs(int now,int fa){
    if(0==ed[head[now]].ne&&now!=1){
        a[now]=Ai[now];
        b[now]=1-Ai[now]-Ar[now];
        c[now]=1-Ai[now]-Ar[now];
        return 1;
    }
    double a1=0,b1=0,c1=0;
    int m=0;
    for(int i=head[now];i;i=ed[i].ne){
        int v=ed[i].to;
        if(++m&&v!=fa){
        if(!dfs(ed[i].to,now)) return 0;
        a1+=a[v];
        b1+=b[v];
        c1+=c[v];
        }
    }
    if(fabs(1-(1-Ai[now]-Ar[now])/m*b1)<1e-9) return 0;
    a[now]=(Ai[now]+(1-Ai[now]-Ar[now])/m*a1)/(1-(1-Ai[now]-Ar[now])/m*b1);
    b[now]=((1-Ai[now]-Ar[now])/m)/(1-(1-Ai[now]-Ar[now])/m*b1);
    c[now]=(1-Ai[now]-Ar[now]+(1-Ai[now]-Ar[now])/m*c1)/(1-(1-Ai[now]-Ar[now])/m*b1);
    return 1;
}
int main(){
    scanf("%d",&t);
    int xx=t;
    while(t--){
         printf("Case %d : ",xx-t);
        memset(head,0,sizeof(head));
        p=0;
        scanf("%d",&n);
        for(int i=1;i<n;++i){
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
    //  cout<<"sdf";
        for(int i=1;i<=n;++i){
            scanf("%lf%lf",&Ai[i],&Ar[i]);
            Ai[i]/=100;
            Ar[i]/=100;
        }
        if(!dfs(1,1)||fabs(1-a[1])<1e-9){
            cout<<"impossiblen";
            continue;
        }
        printf("%.6lfn",c[1]/(1-a[1]));
    }
    return 0;
}