求救P4284（怕没人看）

#include<bits/stdc++.h>
#define double long double 
using namespace std ; 

const int N = 1e6 + 10 ; 
int title[ N ] , tot = 0 ; 
struct node 
{
    int to ; 
    int next ; 
    double cost ; 
} edge[ N ] ; 

void add( int x , int y , double c ) 
{
    edge[ ++ tot ].to = y ; 
    edge[ tot ].next = title[ x ] ; 
    title[ x ] = tot ; 
    edge[ tot ].cost = c ; 
}

double ans = 0 ; 
double f[ N ] , d[ N ] ; 
double cost[ N ] ; 
int n ; 

void dfs( int now_data , int from_data ) 
{
    vector< pair< int , int > > son ; 
    for( int i = title[ now_data ] ; i != -1 ; i = edge[ i ].next ) 
    {
        if( edge[ i ].to == from_data ) continue ; 
        dfs( edge[ i ].to , now_data ) ; 
        f[ now_data ] = f[ now_data ] +  edge[ i ].cost * f[ edge[ i ].to ] - edge[ i ].cost * f[ edge[ i ].to ] * f[ now_data ] ; 
        son.emplace_back( make_pair( edge[ i ].to , edge[ i ].cost ) ) ; 
    }
    double op = 0 ; 
    for( int i = 0 ; i < son.size() ; i ++ ) 
    {
        d[ son[ i ].first ] = op ; 
        op = op + f[ son[ i ].first ] * son[ i ].second - f[ son[ i ].first ] * son[ i ].second * op ; 
    }
    op = 0 ; 
    for( int j = son.size() - 1 ; j >= 0 ; j -- ) 
    {
        d[ son[ j ].first ] = d[ son[ j ].first ] + op - op * d[ son[ j ].first ] ; 
        op = op + f[ son[ j ].first ] * son[ j ].second - op * f[ son[ j ].first ] * son[ j ].second ; 
    }
}
void dfs1( int now_data , int from_data , int cost1 ) 
{
    ans += f[ now_data ] ; 
    for( int i = title[ now_data ] ; i != -1 ; i = edge[ i ].next ) 
    {
        if( edge[ i ].to == from_data ) continue ; 
        double op = d[ edge[ i ].to ] + cost[ now_data ] - cost[ now_data ] * d[ edge[ i ].to ] ; 
        op = op + f[ from_data ] * cost1 - op * f[ from_data ] * cost1 ; 
        f[ now_data ] = op ; 
        f[ edge[ i ].to ] = f[ edge[ i ].to ] + f[ now_data ] * edge[ i ].cost - f[ edge[ i ].to ] * f[ now_data ] * edge[ i ].cost ; 
        dfs1( edge[ i ].to , now_data , edge[ i ].cost ) ; 
    }
}

int main() 
{
    memset( title , -1 , sizeof title ) ; 
    cin >> n ; 
    for( int i = 1 ; i < n ; i ++ ) 
    {
        int x , y , c ; 
        cin >> x >> y >> c ; 
        add( x , y , ( 1.0 * c * 0.01 ) ) ; 
        add( y , x , ( 1.0 * c * 0.01 ) ) ; 
    }
    for( int i = 1 ; i <= n ; i ++ ) 
    {
        int x ; 
        cin >> x ; 
        cost[ i ] = 1.0 * x * 0.01 ; 
        f[ i ] = cost[ i ] ; 
    } 
    dfs( 1 , 0 ) ; 
    dfs1( 1 , 0 , 0 ) ; 
    cout << fixed << setprecision( 6 ) << ans << endl ;    
    return 0 ; 
}