题目：

一眼看上去高斯消元。n^3不行。

竟然直接去看了TJ。发现树型dp。一下想到了自己还没做出的bzoj2878。当然是up和down啦~

然后无限TLE。看看TJ，发现：

　　这个不能直接加的！应该是  自己不亮的概率*它让自己亮的概率  累加到原来亮的概率上！

然后还是无限TLE。

最后发现是N=5e5。应该是N=5e5+5。

PS：因为是那样加的，所以算up的时候不好减；学题解写了前缀和。仔细一想也可以随便解一次方程得出减后的值。

#include
     
      #include
      
       #include
       
        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)*yvoid 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