题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3242
考虑如果图是一棵树的情况，那么理所当然选址是直径的中间，如果是环套树，那么由于最短路组成一棵树，所以是删去环上一条边组成的所有树的直径的最小值的一半，那么我们把环找出来，从中间一出断开，就可以用线段树求出直径在环上的情况，不在环上的情况分开处理即可。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
typedef long long ll ;
const int maxn = 101000 , maxm = 201000 , inf = 0x7fffffff ;
const ll INF = ll( inf ) * ll( inf ) ;
struct edge {
edge *next ;
int t , d ;
} E[ maxm ] ;
edge *pt = E , *head[ maxn ] ;
inline void Init_edge( ) {
memset( head , 0 , sizeof( head ) ) ;
}
inline void add( int s , int t , int d ) {
pt -> t = t , pt -> next = head[ s ] , pt -> d = d ;
head[ s ] = pt ++ ;
}
inline void addedge( int s , int t , int d ) {
add( s , t , d ) , add( t , s , d ) ;
}
int n , sta[ maxn ] , tp = 0 , pos[ maxn ] ;
int ve[ maxn ] , vn = 0 , dn[ maxn ] , nxt[ maxn ] , lst[ maxn ] ;
bool ud[ maxn ] , fg[ maxn ] ;
void getC( int now , int fa ) {
sta[ pos[ now ] = ++ tp ] = now , ud[ now ] = true ;
travel( now ) if ( p -> t != fa ) {
if ( vn ) return ;
dn[ now ] = p -> d ;
if ( ! ud[ p -> t ] ) {
getC( p -> t , now ) ;
} else {
REP( i , pos[ p -> t ] , tp ) {
nxt[ vn ] = dn[ ve[ vn ] = sta[ i ] ] ;
vn ++ ;
}
Rep( i , vn ) lst[ i ] = nxt[ ( i - 1 + vn ) % vn ] , fg[ ve[ i ] ] = true ;
}
}
ud[ now ] = false , tp -- ;
}
inline void upd( ll &x , ll &y , ll a ) {
if ( a > x ) {
y = x ;
x = a ;
} else if ( a > y ) y = a ;
}
inline void upd0( int &v , ll &d , int _v , ll _d ) {
if ( _d > d ) {
d = _d , v = _v ;
}
}
inline void upd1( ll &x , ll y ) {
if ( y > x ) x = y ;
}
ll dep[ maxn ][ 2 ] , dpth[ maxn ] , mh , dist[ maxn ] , ans ;
int mv ;
void geth( int now , int fa ) {
upd0( mv , mh , now , dpth[ now ] ) ;
travel( now ) if ( p -> t != fa && ! fg[ p -> t ] ) {
dpth[ p -> t ] = dpth[ now ] + ll( p -> d ) ;
geth( p -> t , now ) ;
}
}
ll ans0 = 0 ;
inline void upd2( ll &mx , ll &mx0 , ll &mx1 , ll _mx , ll _mx0 , ll _mx1 ) {
mx = max( max( mx , _mx ) , mx0 + _mx1 ) ;
mx0 = max( mx0 , _mx0 ) , mx1 = max( mx1 , _mx1 ) ;
}
struct node {
node *lc , *rc ;
int l , r , mid ;
ll mx , mx0 , mx1 , tag ;
inline void pushdown( ) {
if ( tag ) {
mx0 += tag , mx1 -= tag ;
if ( l < r ) {
lc -> tag += tag , rc -> tag += tag ;
}
tag = 0 ;
}
}
inline void update( ) {
pushdown( ) ;
if ( l < r ) {
lc -> pushdown( ) , rc -> pushdown( ) ;
upd2( mx = lc -> mx , mx0 = lc -> mx0 , mx1 = lc -> mx1 , rc -> mx , rc -> mx0 , rc -> mx1 ) ;
}
}
} sgt[ maxn << 1 ] ;
typedef node* np ;
np ptt = sgt , root ;
void build( int l , int r , np &t ) {
t = ptt ++ ;
t -> l = l , t -> r = r ;
if ( l == r ) {
t -> mx = 0 , t -> mx0 = dep[ l ][ 0 ] - dist[ l ] , t -> mx1 = dep[ l ][ 0 ] + dist[ l ] , t -> tag = 0 ;
return ;
}
t -> mid = ( l + r ) >> 1 ;
build( l , t -> mid , t -> lc ) , build( t -> mid + 1 , r , t -> rc ) ;
t -> update( ) ;
}
void dec( int l , int r , ll d , np t ) {
t -> pushdown( ) ;
if ( t -> l == l && r == t -> r ) {
t -> tag += d ; return ;
}
if ( r <= t -> mid ) dec( l , r , d , t -> lc ) ; else
if ( l > t -> mid ) dec( l , r , d , t -> rc ) ; else
dec( l , t -> mid , d , t -> lc ) , dec( t -> mid + 1 , r , d , t -> rc ) ;
t -> update( ) ;
}
void change( int pos , ll mx0 , ll mx1 , np t ) {
t -> pushdown( ) ;
if ( t -> l == t -> r ) {
t -> mx = 0 , t -> mx0 = mx0 , t -> mx1 = mx1 ; return ;
}
change( pos , mx0 , mx1 , pos <= t -> mid ? t -> lc : t -> rc ) ;
t -> update( ) ;
}
void query( int l , int r , ll &mx , ll &mx0 , ll &mx1 , np t ) {
if ( l > r ) {
mx = mx0 = mx1 = 0 ; return ;
}
t -> pushdown( ) ;
if ( l == t -> l && r == t -> r ) {
mx = t -> mx , mx0 = t -> mx0 , mx1 = t -> mx1 ;
return ;
}
if ( r <= t -> mid ) query( l , r , mx , mx0 , mx1 , t -> lc ) ; else
if ( l > t -> mid ) query( l , r , mx , mx0 , mx1 , t -> rc ) ; else {
query( l , t -> mid , mx , mx0 , mx1 , t -> lc ) ;
ll a , b , c ; query( t -> mid + 1 , r , a , b , c , t -> rc ) ;
upd2( mx , mx0 , mx1 , a , b , c ) ;
}
}
int main( ) {
Init_edge( ) ;
scanf( "%d" , &n ) ;
rep( i , n ) {
int s , t , d ; scanf( "%d%d%d" , &s , &t , &d ) ; addedge( s , t , d ) ;
}
memset( pos , 0 , sizeof( pos ) ) , memset( ud , false , sizeof( ud ) ) , memset( fg , false , sizeof( fg ) ) ;
getC( 1 , 0 ) ;
Rep( i , vn ) {
dep[ i ][ 0 ] = dep[ i ][ 1 ] = 0 ;
int now = ve[ i ] ;
travel( now ) if ( ! fg[ p -> t ] ) {
dpth[ p -> t ] = mh = ll( p -> d ) ;
geth( p -> t , now ) ;
upd( dep[ i ][ 0 ] , dep[ i ][ 1 ] , mh ) ;
dpth[ mv ] = mh = 0 ;
geth( mv , 0 ) ;
upd1( ans , mh ) ;
}
upd1( ans , dep[ i ][ 0 ] + dep[ i ][ 1 ] ) ;
}
ll temp = INF , a , b , c , x , y , z , sum = 0 ;
dist[ 0 ] = 0 ;
REP( i , 1 , ( vn - 1 ) ) dist[ i ] = dist[ i - 1 ] + ll( nxt[ i - 1 ] ) ;
Rep( i , vn ) sum += nxt[ i ] ;
build( 0 , vn - 1 , root ) ;
Rep( i , vn ) {
query( i , vn - 1 , a , b , c , root ) ;
if ( i ) {
query( 0 , i - 1 , x , y , z , root ) ;
upd2( a , b , c , x , y , z ) ;
}
if ( a < temp ) temp = a ;
dec( 0 , vn - 1 , nxt[ i ] , root ) ;
ll d = sum - nxt[ i ] ;
change( i , dep[ i ][ 0 ] - d , dep[ i ][ 0 ] + d , root ) ;
}
ans = max( ans , temp ) ;
printf( "%.1f\n" , double( ans ) / 2.0 ) ;
return 0 ;
}
网友评论