题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3641
首先如果在链上跑的话，可以随便分类讨论之后用持久化线段树搞掉，然后这是一个环套树，那么就树上的情况数链剖分+持久化线段树跑一跑，环上持久化线段树跑一跑，最后注意一下最小的那个点是一个二元环（比赛的时候被这个坑了就没A掉QAQ）。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
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 )
#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )
typedef long double ld ;
const int maxn = 101000 ;
const int maxm = maxn << 1 ;
const int maxu = 500000 ;
struct edge {
int t , x ;
ld l ;
edge *next ;
} E[ maxm ] ;
edge *pe = E , *head[ maxn ] ;
inline void Init_edge( ) {
memset( head , 0 , sizeof( head ) ) ;
}
inline void add( int s , int t , ld l , int x ) {
pe -> t = t , pe -> l = l , pe -> x = x , pe -> next = head[ s ] ;
head[ s ] = pe ++ ;
}
inline void addedge( int s , int t , ld l , int x ) {
add( s , t , l , x ) , add( t , s , l , x ) ;
}
ld V[ maxn ] , W[ maxn ] ;
int n , m , q ;
bool del[ maxn ] , used[ maxn ] ;
int ve[ maxn ] , vn = 0 , sta[ maxn ] , tp = 0 , pos[ maxn ] ;
edge *edg[ maxn ] , *nxt[ maxn ] , *lst[ maxn ] ;
void dfs( int now , int fa ) {
if ( vn ) return ;
used[ now ] = true , sta[ pos[ now ] = ++ tp ] = now ;
travel( now ) if ( p -> t != fa ) {
if ( vn ) return ;
if ( used[ p -> t ] ) {
REP( i , pos[ p -> t ] , tp ) {
ve[ vn ] = sta[ i ] , lst[ vn ] = edg[ sta[ i ] ] , del[ sta[ i ] ] = true ;
vn ++ ;
}
lst[ 0 ] = p ;
return ;
} else {
edg[ p -> t ] = p ;
dfs( p -> t , now ) ;
}
}
used[ now ] = false , -- tp ;
}
struct node {
node *lc , *rc ;
ld x , y ;
node( ) {
x = y = 0 , lc = rc = NULL ;
}
} sgt[ maxn * 20 ] ;
typedef node* np ;
np pt = sgt , null = sgt ;
inline void Init_sgt( ) {
++ pt ;
null -> lc = null -> rc = null , null -> x = null -> y = 0 ;
}
void add( int p , int l , int r , ld x , ld y , np &t , np u ) {
if ( t == null ) t = pt ++ ;
t -> x = u -> x + x , t -> y = u -> y + y ;
if ( l == r ) return ;
int mid = ( l + r ) >> 1 ;
if ( p <= mid ) {
t -> rc = u -> rc ;
add( p , l , mid , x , y , t -> lc = null , u -> lc ) ;
} else {
t -> lc = u -> lc ;
add( p , mid + 1 , r , x , y , t -> rc = null , u -> rc ) ;
}
}
void query( int l , int r , int _l , int _r , ld &x , ld &y , np t ) {
if ( l > r ) {
x = y = 0 ; return ;
}
if ( l == _l && r == _r ) {
x = t -> x , y = t -> y ; return ;
}
int mid = ( _l + _r ) >> 1 ;
if ( r <= mid ) query( l , r , _l , mid , x , y , t -> lc ) ; else
if ( l > mid ) query( l , r , mid + 1 , _r , x , y , t -> rc ) ; else {
ld a , b ;
query( l , mid , _l , mid , x , y , t -> lc ) ;
query( mid + 1 , r , mid + 1 , _r , a , b , t -> rc ) ;
x += a , y += b ;
}
}
int h[ maxn ] , sz[ maxn ] , bel[ maxn ] , chd[ maxn ] , up[ maxn ][ 21 ] , col[ maxn ] , cc = 0 ;
edge *to[ maxn ] ;
vector < int > pth[ maxn ] ;
void getsz( int now , int fa ) {
sz[ now ] = 1 , chd[ now ] = 0 , col[ now ] = cc ;
travel( now ) if ( p -> t != fa && ! del[ p -> t ] ) {
h[ p -> t ] = h[ now ] + 1 , to[ p -> t ] = p , up[ p -> t ][ 0 ] = now ;
getsz( p -> t , now ) ;
sz[ now ] += sz[ p -> t ] ;
if ( ! chd[ now ] || sz[ p -> t ] > sz[ chd[ now ] ] ) chd[ now ] = p -> t ;
}
}
np root[ maxn ] ;
int id[ maxn ] ;
void Link( int now , int fa , int u ) {
id[ now ] = u , root[ now ] = null , pth[ u ].push_back( now ) ;
if ( now != u ) {
ld w = W[ to[ now ] -> x ] , v = V[ to[ now ] -> x ] , l = to[ now ] -> l ;
ld x = ( w * l ) / v , y = w * l ;
add( int( v + 0.1 ) , 1 , maxu , x , y , root[ now ] , root[ fa ] ) ;
}
if ( chd[ now ] ) {
Link( chd[ now ] , now , u ) ;
travel( now ) if ( p -> t != fa && p -> t != chd[ now ] && ! del[ p -> t ] ) {
Link( p -> t , now , p -> t ) ;
}
}
}
inline void Init_lca( ) {
rep( i , 20 ) rep( j , n ) up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;
}
inline int Lca( int u , int v ) {
if ( h[ u ] < h[ v ] ) swap( u , v ) ;
DOWN( i , 20 , 0 ) if ( h[ up[ u ][ i ] ] >= h[ v ] ) u = up[ u ][ i ] ;
if ( v == u ) return v ;
DOWN( i , 20 , 0 ) if ( up[ u ][ i ] != up[ v ][ i ] ) {
u = up[ u ][ i ] , v = up[ v ][ i ] ;
}
return up[ u ][ 0 ] ;
}
inline ld query( int v , int he , int speed ) {
ld x = 0 , y = 0 , a , b ;
while ( h[ v ] > he ) {
if ( h[ id[ v ] ] > he ) {
query( 1 , speed , 1 , maxu , a , b , root[ v ] ) ; x += a ;
query( speed + 1 , maxu , 1 , maxu , a , b , root[ v ] ) ; y += b ;
v = id[ v ] ;
if ( int( V[ to[ v ] -> x ] + 0.1 ) <= speed ) {
a = ( W[ to[ v ] -> x ] * to[ v ] -> l ) / V[ to[ v ] -> x ] ;
x += a ;
} else {
b = W[ to[ v ] -> x ] * to[ v ] -> l ;
y += b ;
}
v = up[ v ][ 0 ] ;
} else {
int c = pth[ id[ v ] ][ he - h[ id[ v ] ] ] ;
query( 1 , speed , 1 , maxu , a , b , root[ v ] ) ; x += a ;
query( speed + 1 , maxu , 1 , maxu , a , b , root[ v ] ) ; y += b ;
query( 1 , speed , 1 , maxu , a , b , root[ c ] ) ; x -= a ;
query( speed + 1 , maxu , 1 , maxu , a , b , root[ c ] ) ; y -= b ;
break ;
}
}
return x + y / ld( speed ) ;
}
inline ld Query( int u , int v , int speed ) {
int lca = Lca( u , v ) ;
return query( u , h[ lca ] , speed ) + query( v , h[ lca ] , speed ) ;
}
np pre[ maxn ] ;
inline ld query_c( int l , int r , int speed ) {
if ( l > r ) return 0 ;
ld x = 0 , y = 0 , a , b ;
query( 1 , speed , 1 , maxu , a , b , pre[ r ] ) ; x += a ;
query( speed + 1 , maxu , 1 , maxu , a , b , pre[ r ] ) ; y += b ;
query( 1 , speed , 1 , maxu , a , b , pre[ l ] ) ; x -= a ;
query( speed + 1 , maxu , 1 , maxu , a , b , pre[ l ] ) ; y -= b ;
return x + y / ld( speed ) ;
}
inline ld query_p( int p , int speed ) {
ld x = 0 , y = 0 , a , b ;
query( 1 , speed , 1 , maxu , a , b , pre[ p ] ) ; x += a ;
query( speed + 1 , maxu , 1 , maxu , a , b , pre[ p ] ) ; y += b ;
return x + y / ld( speed ) ;
}
inline ld cal( edge *p , int spd ) {
return ( W[ p -> x ] * p -> l ) / min( ld( spd ) , V[ p -> x ] ) ;
}
int main( ) {
Init_edge( ) , Init_sgt( ) ;
scanf( "%d%d%d" , &n , &m , &q ) ;
int s , t , x ; ld l ;
double A , B ;
rep( i , n ) {
scanf( "%d%d%lf%d" , &s , &t , &A , &x ) ;
l = A ;
addedge( s , t , l , x ) ;
}
rep( i , m ) {
scanf( "%lf%lf" , &A , &B ) ;
V[ i ] = A , W[ i ] = B ;
}
if ( n == 2 ) {
while ( q -- ) {
scanf( "%d%d%d" , &s , &t , &x ) ;
if ( s == t ) {
printf( "0.000000\n" ) ; continue ;
}
double ans = min( cal( head[ s ] , x ) , cal( head[ s ] -> next , x ) ) ;
printf( "%.6f\n" , ans ) ;
}
return 0 ;
}
memset( del , false , sizeof( del ) ) , memset( used , false , sizeof( used ) ) ;
dfs( 1 , 0 ) ;
Rep( i , vn ) pos[ ve[ i ] ] = i ;
memset( h , 0 , sizeof( h ) ) , memset( up , 0 , sizeof( up ) ) , memset( col , 0 , sizeof( col ) ) ;
Rep( i , vn ) travel( ve[ i ] ) if ( ! del[ p -> t ] ) {
to[ p -> t ] = p , bel[ p -> t ] = ve[ i ] ;
h[ p -> t ] = 1 , root[ p -> t ] = null , ++ cc ;
getsz( p -> t , 0 ) ;
Link( p -> t , 0 , p -> t ) ;
}
ld X , Y , a , b ;
a = V[ lst[ 0 ] -> x ] , b = W[ lst[ 0 ] -> x ] ;
X = ( b * lst[ 0 ] -> l ) / a , Y = b * lst[ 0 ] -> l ;
add( int( a + 0.1 ) , 1 , maxu , X , Y , pre[ 0 ] = null , null ) ;
REP( i , 1 , ( vn - 1 ) ) {
a = W[ lst[ i ] -> x ] , b = V[ lst[ i ] -> x ] ;
X = ( a * lst[ i ] -> l ) / b , Y = a * lst[ i ] -> l ;
add( int( b + 0.1 ) , 1 , maxu , X , Y , pre[ i ] = null , pre[ i - 1 ] ) ;
}
Init_lca( ) ;
ld ans ;
while ( q -- ) {
scanf( "%d%d%d" , &s , &t , &x ) ;
if ( col[ s ] == col[ t ] && ! del[ s ] ) {
ans = Query( s , t , x ) ;
} else {
ans = 0 ;
if ( ! del[ s ] ) {
ans += query( s , 1 , x ) ;
DOWN( i , 20 , 0 ) if ( h[ up[ s ][ i ] ] > 1 ) {
s = up[ s ][ i ] ;
}
if ( h[ s ] > 1 ) s = up[ s ][ 0 ] ;
ans += cal( to[ s ] , x ) ;
s = bel[ s ] ;
}
if ( ! del[ t ] ) {
ans += query( t , 1 , x ) ;
DOWN( i , 20 , 0 ) if ( h[ up[ t ][ i ] ] > 1 ) {
t = up[ t ][ i ] ;
}
if ( h[ t ] > 1 ) t = up[ t ][ 0 ] ;
ans += cal( to[ t ] , x ) ;
t = bel[ t ] ;
}
s = pos[ s ] , t = pos[ t ] ;
if ( s > t ) swap( s , t ) ;
ans += min( query_c( s , t , x ) , query_c( t , vn - 1 , x ) + query_p( s , x ) ) ;
}
printf( "%.6f\n" , double( ans ) ) ;
}
return 0 ;
}
网友评论