题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2878

在树上维护两个东西up(v),down(v),表示向上和向下的期望长度，n=m的话就把环搞出来，弄成个环套树，然后DP即可。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

  

using namespace std ;

  

#define travel( x ) for ( vector < edge > :: iterator p = E[ x ].begin(  ) ; p != E[ x ].end(  ) ; ++ p )

#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  

#define addedge( s , t , d ) add( s , t , d ) , add( t , s , d )

#define add( s , t , d ) E[ s ].push_back( edge( t , d ) )

  

const int maxn = 100100 ;

  

struct edge {

    int t , d ; 

    edge( int _t , int _d ) : t( _t ) , d( _d ) {

    }

} ;

vector < edge > E[ maxn ] ;

  

double sum[ maxn ] , down[ maxn ] , up[ maxn ] , cnt[ maxn ] , d[ maxn ] ;

bool used[ maxn ] ;

  

void dp_down( int now , int fa ) {

    cnt[ now ] = sum[ now ] = 0 ; 

    travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {

        cnt[ now ] += 1 ; 

        dp_down( p -> t , now ) ;

        sum[ now ] += double( p -> d ) + down[ p -> t ] ;

    }

    if ( cnt[ now ] ) down[ now ] = sum[ now ] / cnt[ now ] ;

}

  

void dp_up( int now , int fa ) {

    travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {

        if ( d[ now ] > 1.000001 ) up[ p -> t ] = double( p -> d ) + ( sum[ now ] - double( p -> d ) - down[ p -> t ] + up[ now ] ) / ( d[ now ] - 1 ) ; else up[ p -> t ] = double( p -> d ) + up[ now ] ;

        dp_up( p -> t , now ) ;

    }

}

  

int n , m ; 

  

double solve0(  ) {

    memset( used , false , sizeof( used ) ) ;

    dp_down( 1 , 0 ) ;

    dp_up( 1 , 0 ) ;

    double ans = 0 ; 

    rep( i , n ) ans += ( sum[ i ] + up[ i ] ) / d[ i ] ;

    return ans / double( n ) ;

}

  

bool flag = false ;

int Stack[ maxn ] , Cnt = 0 , len , node[ maxn ] ;

double D[ maxn ] , dist[ maxn ] ;

  

void dfs( int now , int fa ) {

    if ( flag ) return ; 

    used[ now ] = true , Stack[ Cnt ++ ] = now ;

    travel( now ) if ( p -> t != fa ) if ( used[ p -> t ] ) {

        if ( flag ) return ; 

        int i ;

        for ( i = 0 ; i < Cnt && Stack[ i ] != p -> t ; ++ i ) ;

        len = 0 ; 

        for ( ; i < Cnt ; ++ i ) {

            node[ len ] = Stack[ i ] ;

            dist[ len ++ ] = D[ i ] ;

        }

        dist[ len - 1 ] = double( p -> d ) ;

        flag = true ;

        return ; 

    } else {

        D[ Cnt - 1 ] = double( p -> d ) ;

        dfs( p -> t , now ) ;

    }

    used[ now ] = false , -- Cnt ;

}

  

double left[ maxn ] , right[ maxn ] ;

  

double solve1(  ) {

    memset( used , false , sizeof( used ) ) ;

    dfs( 1 , 0 ) ;

    memset( used , false , sizeof( used ) ) ;

    for ( int i = 0 ; i < len ; ++ i ) used[ node[ i ] ] = true ;

    for ( int i = 0 ; i < len ; ++ i ) dp_down( node[ i ] , 0 ) ;

    memset( left , 0 , sizeof( left ) ) ;

    memset( right , 0 , sizeof( right ) ) ;

    for ( int i = 0 ; i < len ; ++ i ) {

        left[ i ] = right[ i ] = 0 ; 

        for ( int p = i , j = ( i + 1 ) % len ; j != i ; ( j += 1 ) %= len , ( p += 1 ) %= len ) {

            if ( d[ node[ p ] ] < 2.01 || p != i ) left[ j ] = dist[ p ] + ( ( left[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 1 ) ) ;

            else left[ j ] = dist[ p ] + ( ( left[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 2 ) ) ;

        }

        for ( int p = i , j = ( i - 1 + len ) % len ; j != i ; j = ( j - 1 + len ) % len , p = ( p - 1 + len ) % len ) {

            if ( d[ node[ p ] ] < 2.01 || p != i ) right[ j ] = dist[ j ] + ( right[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 1 ) ;

            else right[ j ] = dist[ j ] + ( right[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 2 ) ;

        }

        up[ node[ ( i - 1 + len ) % len ] ] += left[ ( i - 1 + len ) % len ] ;

        up[ node[ ( i + 1 ) % len ] ] += right[ ( i + 1 ) % len ] ;

    }

    for ( int i = 0 ; i < len ; ++ i ) dp_up( node[ i ] , 0 ) ;

    double ans = 0 ; 

    for ( int i = 0 ; i ++ < n ; ) ans += ( up[ i ] + sum[ i ] ) / d[ i ] ;

    return ans / double( n ) ;

}

  

int main(  ) {

    scanf( "%d%d" , &n , &m ) ;

    rep( i , m ) {

        int s , t , w ; scanf( "%d%d%d" , &s , &t , &w ) ;

        d[ s ] += 1, d[ t ] += 1 , addedge( s , t , w ) ;

    }

    if ( m == n - 1 ) printf( "%.5f\n" , solve0(  ) ) ; else printf( "%.5f\n" , solve1(  ) ) ;

    return 0 ;

}