C++(g++ 7.5.0) 解法, 执行用时: 59ms, 内存消耗: 48120K, 提交时间: 2022-11-01 21:44:23

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000010;
vector<int> g[N];
double e[N],k[N];
double A[N],b[N],B[N];
int flag=1;
double eps=1e-9;
void dfs(int x,int fa)
{
    A[x]=k[x];
    b[x]=B[x]=1.0-k[x]-B[x];
    double suma=0,sumb=0,sumc=0;
    int son=0;
    
    for(auto to:g[x])
    {
        if(to==fa) continue;
        dfs(to,x);
        suma+=A[to];
        sumb+=b[to];
        sumc+=B[to];
        son++;
    }
 
        double p=(1-k[x]-e[x])/(g[x].size());
        if(fabs(1-p*sumb)<eps)
        {
            flag=0;
            return ;
        }
        A[x]=(k[x]+p*suma)/(1-p*sumb);
        b[x]=p/(1-p*sumb);
        B[x]=(p*sumc+p*g[x].size())/(1-p*sumb);
    
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        k[i]=x*1.0/100;
        e[i]=y*1.0/100;
    }
    dfs(1,0);
    printf("%.10lf",B[1]/(1-A[1]));
}

C++(clang++ 11.0.1) 解法, 执行用时: 7ms, 内存消耗: 1280K, 提交时间: 2022-12-07 20:48:09

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    return x;
}
vector<int>f[10010];
int n,a[10004],b[10004];
double A[10004],B[10004],C[10004];
void dfs(int x,int fa){
	A[x]=1.0*b[x]/100;
	B[x]=1.0*a[x]/100;
	int siz=f[x].size();
	C[x]=1.0*a[x]/100/siz;
	double k=1;
	for(int y:f[x]){
		if(y==fa)continue;
		dfs(y,x);
		A[x]+=A[y]*a[x]/100/siz;
		B[x]+=B[y]*a[x]/100/siz;
		k-=C[y]*a[x]/100/siz;
	}
	A[x]/=k;
	B[x]/=k;
	C[x]/=k;
	return;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
    	int u=read(),v=read();
    	f[u].push_back(v);
    	f[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		b[i]=read();
		a[i]=100-b[i]-read();
	}
	dfs(1,0);
	printf("%.13lf",B[1]/(1.0-A[1]));
	return 0;
}