BZOJ-1509: [NOI2003]逃学的小孩（树DP）

题目：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 ;

}