题目: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 ;
}
网友评论