BZOJ 3566 / Luogu P4284

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 500005
#define eps 1e-7
using namespace std;

struct node{
    int v,nxt,w;
}e[M<<1];
int num,n,m;
int a[M],head[M],deep[M];
double h[M];
double ans;

inline int read(){
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
      x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}

inline void add_edge(int x,int y,int z){
    e[++num].v=y;
    e[num].nxt=head[x];
    e[num].w=z;
    head[x]=num;
}

void dfs(int x){
    for(int i=head[x];i;i=e[i].nxt)
    if(!deep[e[i].v]){
        deep[e[i].v]=deep[x]+1;
        dfs(e[i].v);
        double k=h[e[i].v]*double(e[i].w)/100;
        h[x]=h[x]+k-h[x]*k;
    }
}

inline int check(double aa,double bb){
    if(aa+eps>bb&&aa-eps<bb) return 1;
    return 0;
}

void redfs(int x){
    ans+=h[x];
    for(int i=head[x];i;i=e[i].nxt)
    if(deep[e[i].v]>deep[x]){
        if(check(h[e[i].v]*double(e[i].w)/100,1)){
            redfs(e[i].v);
            continue;
        }
        double k=(h[x]-h[e[i].v]*double(e[i].w)/100)/(1-h[e[i].v]*double(e[i].w)/100);
        k*=double(e[i].w)/100;
        h[e[i].v]=h[e[i].v]+k-k*h[e[i].v];
        redfs(e[i].v);
    }
}

int main(){
    n=read();
    int x,y,z;
    for(int i=1;i<n;i++){
        x=read();
        y=read();
        z=read();
        add_edge(x,y,z),add_edge(y,x,z);
    }
    for(int i=1;i<=n;i++)
        a[i]=read(),h[i]=a[i]*0.01;
    deep[1]=1;
    dfs(1);
    redfs(1);
    printf("%.6lf",ans);
    return 0;
}