题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3566
一眼看上去高斯消元。n^3不行。
竟然直接去看了TJ。发现树型dp。一下想到了自己还没做出的bzoj2878。当然是up和down啦~
然后无限TLE。看看TJ，发现：
这个不能直接加的！应该是 自己不亮的概率*它让自己亮的概率 累加到原来亮的概率上！
然后还是无限TLE。
最后发现是N=5e5。应该是N=5e5+5。
PS：因为是那样加的，所以算up的时候不好减；学题解写了前缀和。仔细一想也可以随便解一次方程得出减后的值。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=5e5+5; int n,head[N],xnt,stack[N],top; double e[N],q[N],up[N],dn[N],ans,sum[2][N];// struct Edge{ int next,to;double w; Edge(int n=0,int t=0,double k=0.0):next(n),to(t),w(k) {} }edge[N<<1]; void add(int x,int y,double z) { edge[++xnt]=Edge(head[x],y,z);head[x]=xnt; edge[++xnt]=Edge(head[y],x,z);head[y]=xnt; } double pls(double x,double y){return x+y-x*y;}//x+(1-x)*y void dfs1(int cr,int f) { for(int i=head[cr],v;i;i=edge[i].next) if((v=edge[i].to)!=f) { dfs1(v,cr); dn[cr]=pls(dn[cr],pls(dn[v],q[v])*edge[i].w); } } void dfs2(int cr,int f) { up[cr]=pls(up[cr],q[cr]); ans+=pls(up[cr],dn[cr]); top=0; for(int i=head[cr];i;i=edge[i].next) if(edge[i].to!=f) {stack[++top]=edge[i].to;e[top]=edge[i].w;} sum[0][0]=0;sum[1][top+1]=0;// for(int i=1;i<=top;i++)sum[0][i]=pls(sum[0][i-1],pls(dn[stack[i]],q[stack[i]])*e[i]); for(int i=top;i;i--)sum[1][i]=pls(sum[1][i+1],pls(dn[stack[i]],q[stack[i]])*e[i]); for(int i=1;i<=top;i++)up[stack[i]]=pls(pls(sum[0][i-1],sum[1][i+1]),up[cr])*e[i]; for(int i=head[cr];i;i=edge[i].next) if(edge[i].to!=f)dfs2(edge[i].to,cr); } int main() { scanf("%d",&n);int x,y;double z; for(int i=1;i<n;i++) { scanf("%d%d%lf",&x,&y,&z); add(x,y,z/100); } for(int i=1;i<=n;i++)scanf("%lf",&q[i]),q[i]/=100; dfs1(1,0);dfs2(1,0); printf("%.6lf ",ans); return 0; }