这题点数很大，难以高斯消元
可是仔细想想一定要用吗？对于根节点他的概率可以通过子节点算出来
补集转化，设f[i]表示当前点没电的概率
对于孩子对父亲的贡献：f[x]=(1-q[x])*∏ 1-(1-f[y])*a[k].d
但是现在除了根以外其他的都不是真正的值，再dfs一次把父亲的贡献也算上，注意去掉自己的贡献
f[y]*=(1-(1-f[x]/((1-f[y])*a[k].d))*a[k].d)
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node { int x,y,next;double d; }a[1100000];int len,last[510000]; void ins(int x,int y,double d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } double q[510000],f[510000]; void dfs1(int x,int fr) { f[x]=1-q[x]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr) { dfs1(y,x); f[x]*=1-(1-f[y])*a[k].d; } } } void dfs2(int x,int fr) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr) { if((1-(1-f[y])*a[k].d)>1e-8) { double r=1-f[x]/(1-(1-f[y])*a[k].d); f[y]*=(1-r*a[k].d); } dfs2(y,x); } } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,x,y;double dd; scanf("%d",&n); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { scanf("%d%d%lf",&x,&y,&dd);dd/=100; ins(x,y,dd),ins(y,x,dd); } for(int i=1;i<=n;i++) scanf("%lf",&q[i]), q[i]/=100; dfs1(1,0); dfs2(1,0); double ans=0; for(int i=1;i<=n;i++)ans+=1-f[i]; printf("%.6lf ",ans); return 0; }