题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1758
分数规划问题，经典做法二分答案，然后由于是树的路径问题，所以在点分治里面套一个二分，然后对于求max{a[i]+b[j]}(L<=i+j<=R)，转化成( L-i <= j <= R-i )，那么就出现一个左右端点都单调的RMQ问题，那就单调队列，然后由于树分治每次递归调用的复杂度必须只与子树的大小相关，那么必须按照当前分治的重心的子树最大高度从小到大枚举子树，这样才能保证总共的复杂度为O(n log n log MaxV)。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std ;
#define addedge( s , t , d ) add( s , t , d ) , add( t , s , d )
#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 , a , b ) for ( int i = a ; i <= b ; ++ i )
#define DOWN( i , b , a ) for ( int i = b ; i >= a ; -- i )
const int maxn = 101000 , inf = 100000000 ;
const double esp = 0.0001 ;
struct edge {
int t , d ;
edge *next ;
} E[ maxn << 1 ] ;
edge *pt = E , *Head[ maxn ] ;
void add( int s , int t , int d ) {
edge *p = pt ++ ;
p -> t = t , p -> d = d , p -> next = Head[ s ] ;
Head[ s ] = p ;
}
double ans = 0 ;
bool used[ maxn ] ;
int n , L , R ;
int size[ maxn ] , maxw , h[ maxn ] , maxh[ maxn ] , MAXH , root ;
double dep[ maxn ] ;
vector < int > sub[ maxn ] , tub[ maxn ] ;
inline void Upd( int &pos , int val ) {
if ( val > pos ) pos = val ;
}
inline void upd( double &pos , double val ) {
if ( val > pos ) pos = val ;
}
void getsize( int now , int fa ) {
size[ now ] = 1 ;
travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {
getsize( p -> t , now ) , Upd( maxw , p -> d ) ;
size[ now ] += size[ p -> t ] ;
}
}
int q[ maxn ][ 2 ] , head , tail ;
inline void getroot( int now ) {
bool flag ;
int ve , pre , si = size[ now ] >> 1 ;
q[ tail = 1 ][ 0 ] = now , q[ 1 ][ 1 ] = 0 , head = 0 ;
for ( ; head < tail ; ) {
flag = true ;
ve = q[ ++ head ][ 0 ] ; pre = q[ head ][ 1 ] ;
if ( size[ now ] - size[ ve ] > si ) flag = false ;
travel( ve ) if ( p -> t != pre && ! used[ p -> t ] ) {
if ( size[ p -> t ] > si ) flag = false ;
q[ ++ tail ][ 0 ] = p -> t ; q[ tail ][ 1 ] = ve ;
}
if ( flag ) {
root = ve ; return ;
}
}
}
void geth( int now , int fa , int num ) {
Upd( maxh[ num ] , h[ now ] ) , sub[ num ].push_back( now ) , Upd( MAXH , h[ now ] ) ;
travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {
h[ p -> t ] = h[ now ] + 1 , dep[ p -> t ] = dep[ now ] + p -> d ;
geth( p -> t , now , num ) ;
}
}
double dp[ maxn ] , fun[ maxn ] ;
int Q[ maxn ] ;
inline bool check( double mid ) {
REP( i , 0 , MAXH ) dp[ i ] = - inf ; dp[ 0 ] = 0 ;
double temp = - inf ;
int v , u , left , right , ret ;
REP( i , 0 , MAXH ) {
DOWN( k , tub[ i ].size( ) - 1 , 0 ) {
v = tub[ i ][ k ] ;
REP( j , 0 , maxh[ v ] ) fun[ j ] = - inf ;
REP( j , 0 , ( sub[ v ].size( ) - 1 ) ) {
u = sub[ v ][ j ] ;
upd( fun[ h[ u ] ] , dep[ u ] - double( h[ u ] ) * mid ) ;
}
head = 1 , tail = 0 ;
left = max( L - maxh[ v ] , 0 ) , right = min( R - maxh[ v ] , maxh[ v ] ) ;
REP( j , left , right ) {
for ( ; head <= tail && dp[ Q[ tail ] ] <= dp[ j ] ; -- tail ) ;
Q[ ++ tail ] = j ;
}
DOWN( j , maxh[ v ] , 0 ) {
for ( ; head <= tail && Q[ head ] < L - j ; ++ head ) ;
if ( head <= tail ) upd( temp , fun[ j ] + dp[ Q[ head ] ] ) ;
if ( R - ( j - 1 ) <= maxh[ v ] ) {
for ( ; head <= tail && dp[ Q[ tail ] ] <= dp[ R - ( j - 1 ) ] ; -- tail ) ;
Q[ ++ tail ] = R - ( j - 1 ) ;
}
}
REP( j , 0 , maxh[ v ] ) upd( dp[ j ] , fun[ j ] ) ;
if ( temp >= 0 ) return true ;
}
}
return false ;
}
void solve( int now ) {
maxw = 0 ; getsize( now , 0 ) ; getroot( now ) ;
h[ root ] = dep[ root ] = 0 , MAXH = 0 ;
travel( root ) if ( ! used[ p -> t ] ) {
h[ p -> t ] = 1 , dep[ p -> t ] = p -> d , maxh[ p -> t ] = 0 , sub[ p -> t ].clear( ) ;
geth( p -> t , root , p -> t ) ;
}
REP( i , 0 , MAXH ) tub[ i ].clear( ) ;
travel( root ) if ( ! used[ p -> t ] ) tub[ maxh[ p -> t ] ].push_back( p -> t ) ;
double l = 0 , r = maxw , mid ;
while ( r - l > esp ) {
mid = ( l + r ) / 2.0 ;
if ( check( mid ) ) l = mid ; else r = mid ;
}
upd( ans , l ) , used[ root ] = true ;
travel( root ) if ( ! used[ p -> t ] ) {
solve( p -> t ) ;
}
}
int main( ) {
memset( Head , 0 , sizeof( Head ) ) ;
scanf( "%d%d%d" , &n , &L , &R ) ;
REP( i , 2 , n ) {
int s , t , d ; scanf( "%d%d%d" , &s , &t , &d ) ; addedge( s , t , d ) ;
}
memset( used , false , sizeof( used ) ) ;
solve( 1 ) ;
printf( "%.3f\n" , ans ) ;
return 0 ;
}
网友评论