BZOJ-1509: [NOI2003]逃学的小孩(树DP)

作者: AmadeusChan | 来源:发表于2019-03-15 09:56 被阅读0次

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

    难得的水题啊~

    我们可以发现,最优解一定是A,B的链中间长出一个C(或者连到C的链)(反证),这样我们可以枚举他们中间的那个点,然后用树DP预先算出某个点向上连出的最长链长度,向下连出的最长链长度,每次枚举的时候选出改点最长的三条链分别为a,b,c,那么答案就是a+b+c+min(a,b)。

    代码:

    #include <cstdio>
    
    #include <algorithm>
    
    #include <cstring>
    
      
    
    using namespace std ;
    
      
    
    #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )
    
    #define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
    
    #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
    
    #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
    
      
    
    const int maxn = 201000 ;
    
    const int maxm = 401000 ;
    
      
    
    struct edge {
    
            edge *next ;
    
            int t , d ;
    
    } E[ maxm ] ;
    
      
    
    edge *pt = E , *head[ maxn ] ;
    
      
    
    inline void add( int s , int t , int d ) {
    
            pt -> t = t , pt -> d = d , pt -> next = head[ s ] ; head[ s ] = pt ++ ;
    
    }
    
      
    
    inline void addedge( int s , int t , int d ) {
    
            add( s , t , d ) , add( t , s , d ) ;
    
    }
    
      
    
    int n , m ;
    
      
    
    typedef long long ll ;
    
      
    
    ll dp[ maxn ][ 2 ] , ans = 0 , D[ maxn ] ;
    
    int ch[ maxn ] ;
    
      
    
    #define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )
    
      
    
    void dfs0( int now , int fa ) {
    
            ll ret = 0 ;
    
            travel( now ) if ( p -> t != fa ) {
    
                    dfs0( p -> t , now ) ; ret = max( ret , dp[ p -> t ][ 0 ] + ll( p -> d ) ) ;
    
            }
    
            dp[ now ][ 0 ] = ret ;
    
    }
    
      
    
    void dfs1( int now , int fa ) {
    
            ll mx = dp[ now ][ 1 ] ;
    
            int cnt = 0 , v ;
    
            travel( now ) if ( p -> t != fa ) {
    
                    ch[ ++ cnt ] = p -> t ; D[ cnt ] = p -> d ;
    
                    dp[ p -> t ][ 1 ] = mx + ll( p -> d ) ;
    
                    mx = max( mx , dp[ p -> t ][ 0 ] + ll( p -> d ) ) ;
    
            }
    
            mx = dp[ now ][ 1 ] ;
    
            DOWN( i , cnt , 1 ) {
    
                    v = ch[ i ] ;
    
                    dp[ v ][ 1 ] = max( dp[ v ][ 1 ] , mx + D[ i ] ) ;
    
                    mx = max( mx , dp[ v ][ 0 ] + D[ i ] ) ;
    
            }
    
            travel( now ) if ( p -> t != fa ) dfs1( p -> t , now ) ;
    
    }
    
      
    
    void dfs2( int now , int fa ) {
    
            ll a = dp[ now ][ 1 ] , b = 0 , c = 0 , cost ;
    
            travel( now ) if ( p -> t != fa ) {
    
                    if ( ( cost = dp[ p -> t ][ 0 ] + ll( p -> d ) ) > a ) {
    
                            c = b ; b = a ; a = cost ;
    
                    } else if ( cost > b ) {
    
                            c = b ; b = cost ;
    
                    } else if ( cost > c ) c = cost ;
    
            }
    
            ans = max( ans , c + a + b + min( a , b ) ) ;
    
            travel( now ) if ( p -> t != fa ) dfs2( p -> t , now ) ;
    
    }
    
      
    
    int main(  ) {
    
            scanf( "%d%d" , &n , &m ) ;
    
            memset( head , 0 , sizeof( head ) ) ;
    
            while ( m -- ) {
    
                    int s , t , d ; scanf( "%d%d%d" , &s , &t , &d ) ; addedge( s , t , d ) ;
    
            }
    
            dfs0( 1 , 0 ) ; dp[ 1 ][ 1 ] = 0 ; dfs1( 1 , 0 ) ; dfs2( 1 , 0 ) ;
    
            printf( "%lld\n" , ans ) ;
    
            return 0 ;
    
    }
    

    相关文章

      网友评论

        本文标题:BZOJ-1509: [NOI2003]逃学的小孩(树DP)

        本文链接:https://www.haomeiwen.com/subject/qsokmqtx.html