题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2631
本来是裸的LCT的说，程序写丑了T了N次，在无数次常数优化之后终于以神奇的时间A了。。。
adaf2edda3cc7cd9e389089c3b01213fb90e91ca.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define maxn 100100
#define mod 51061
#define check( ch ) ( ch == '+' || ch == '-' || ch == '*' || ch == '/' || ( ch >= '0' && ch <= '9' ) )
#define ll unsigned int
#define AddEdge( s , t ) Add( s , t ) , Add( t , s )
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define F( t ) father[ t ]
#define G( t ) F( F( t ) )
#define P( t ) parent[ splay_roof( t ) ]
#define V( t ) value[ t ]
#define sum( t ) sum[ t ]
#define S( t ) size[ t ]
#define fa( t ) flag_a[ t ]
#define fb( t ) flag_b[ t ]
#define fr( t ) flag_r[ t ]
#define C( t ) ( t == L( F( t ) ) )
int left[ maxn ] , right[ maxn ] , father[ maxn ] , parent[ maxn ] ;
ll value[ maxn ] , sum[ maxn ] , size[ maxn ] , flag_a[ maxn ] , flag_b[ maxn ] ;
bool flag_r[ maxn ] ;
void sign( int t , ll a , ll b ) {
if ( ! t ) return ;
fa( t ) = ( fa( t ) * a ) % mod ;
fb( t ) = ( fb( t ) * a + b ) % mod ;
}
void pushdown( int t ) {
if ( t ) {
if ( fa( t ) != 1 || fb( t ) != 0 ) {
V( t ) = ( V( t ) * fa( t ) + fb( t ) ) % mod ;
sum( t ) = ( sum( t ) * fa( t ) + S( t ) * fb( t ) ) % mod ;
sign( L( t ) , fa( t ) , fb( t ) ) , sign( R( t ) , fa( t ) , fb( t ) ) ;
fa( t ) = 1 , fb( t ) = 0 ;
}
if ( fr( t ) ) {
swap( L( t ) , R( t ) ) ;
fr( t ) ^= true , fr( L( t ) ) ^= true , fr( R( t ) ) ^= true ;
}
}
}
void update( int t ) {
pushdown( t ) ; pushdown( L( t ) ) , pushdown( R( t ) ) ;
S( t ) = ( S( L( t ) ) + S( R( t ) ) + 1 ) % mod ;
sum( t ) = ( sum( L( t ) ) + sum( R( t ) ) + V( t ) ) % mod ;
}
void zag( int t ) {
pushdown( t ) ; pushdown( R( t ) ) ;
int k = R( t ) , u = F( t ) ; bool flag = C( t ) ;
F( R( t ) = L( k ) ) = t ; update( t ) ;
F( L( k ) = t ) = k ; update( k ) ;
F( k ) = u ; if ( u ) if ( flag ) L( u ) = k ; else R( u ) = k ;
}
void zig( int t ) {
pushdown( t ) ; pushdown( L( t ) ) ;
int k = L( t ) , u = F( t ) ; bool flag = C( t ) ;
F( L( t ) = R( k ) ) = t ; update( t ) ;
F( R( k ) = t ) = k ; update( k ) ;
F( k ) = u ; if ( u ) if ( flag ) L( u ) = k ; else R( u ) = k ;
}
void splay( int t ) {
while ( F( t ) ) {
pushdown( G( t ) ) ; pushdown( F( t ) ) ; pushdown( t ) ;
if ( ! G( t ) ) if ( C( t ) ) zig( F( t ) ) ; else zag( F( t ) ) ;
else {
if ( C( t ) ) {
if ( C( F( t ) ) ) zig( G( t ) ) ; zig( F( t ) ) ;
} else {
if ( ! C( F( t ) ) ) zag( G( t ) ) ; zag( F( t ) ) ;
}
}
}
}
int Min( int t ) {
pushdown( t ) ;
while ( L( t ) ) {
pushdown( t = L( t ) ) ;
}
return t ;
}
int splay_roof( int t ) {
splay( t ) ;
return Min( t ) ;
}
int Access( int v ) {
int u = 0 ;
do {
splay( v ) ; pushdown( v ) ;
F( R( v ) ) = 0 ; P( R( v ) ) = v ;
F( R( v ) = u ) = v ; update( v ) ;
u = v ; v = P( v ) ;
} while ( v ) ;
return u ;
}
void make( int t ) {
L( t ) = R( t ) = F( t ) = parent[ t ] = 0 ;
V( t ) = sum( t ) = S( t ) = 1 ;
fa( t ) = 1 , fb( t ) = 0 , fr( t ) = false ;
}
void Join( int v , int u ) {
P( v ) = u ;
}
void Cut( int v ) {
Access( v ) ;
splay( v ) ; pushdown( v ) ;
F( L( v ) ) = 0 ; L( v ) = 0 ; P( v ) = 0 ; update( v ) ;
}
int Roof( int v ) {
Access( v ) ;
return splay_roof( v ) ;
}
struct edge {
edge *next ;
int t ;
} *head[ maxn ] ;
void Add( int s , int t ) {
edge *p = new( edge ) ;
p -> t = t , p -> next = head[ s ] ;
head[ s ] = p ;
}
int n , m , fath[ maxn ] ;
bool f[ maxn ] ;
void dfs( int v ) {
f[ v ] = false ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
fath[ p -> t ] = v ;
dfs( p -> t ) ;
}
}
void getint( int &t ) {
int ch ; for ( ch = getchar( ) ; ! check( ch ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; check( ch ) ; ch = getchar( ) ) {
t *= 10 , t += ch - '0' ;
}
}
void getll( ll &t ) {
int ch ; for ( ch = getchar( ) ; ! check( ch ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; check( ch ) ; ch = getchar( ) ) {
t *= 10 , t += ch - '0' ;
}
}
int out[ 20 ] ;
void putll( ll t ) {
if ( ! t ) putchar( '0' ) ; else {
out[ 0 ] = 0 ;
for ( ; t ; t /= 10 ) out[ ++ out[ 0 ] ] = t % 10 ;
for ( int i = out[ 0 ] ; i ; -- i ) putchar( '0' + out[ i ] ) ;
}
putchar( '\n' ) ;
}
int main( ) {
memset( head , 0 , sizeof( head ) ) ;
getint( n ) , getint( m ) ;
for ( int i = 1 ; i < n ; ++ i ) {
int s , t ; getint( s ) , getint( t ) ;
AddEdge( s , t ) ;
}
memset( f , true , sizeof( f ) ) ;
L( 0 ) = R( 0 ) = F( 0 ) = parent[ 0 ] = 0 ;
S( 0 ) = V( 0 ) = sum( 0 ) = 0 ;
for ( int i = 0 ; i ++ < n ; ) make( i ) ;
dfs( 1 ) ;
for ( int i = 2 ; i <= n ; ++ i ) P( i ) = fath[ i ] ;
while ( m -- ) {
int ch ; for ( ch = getchar( ) ; ! check( ch ) ; ch = getchar( ) ) ;
if ( ch == '+' ) {
int u , v ; ll c ; getint( u ) , getint( v ) ; getll( c ) ;
Access( u ) ;
int lca = Access( v ) ;
splay( lca ) ; pushdown( lca ) ;
( V( lca ) += c ) %= mod ;
sign( R( lca ) , 1 , c ) ;
update( lca ) ;
if ( lca != u ) {
splay( u ) ;
sign( u , 1 , c ) ;
}
} else if ( ch == '-' ) {
int x , y , u , v ; getint( x ) , getint( y ) , getint( u ) , getint( v ) ;
Access( x ) ;
int lca = Access( y ) ;
if ( lca == x ) {
Cut( y ) ;
if ( Roof( u ) == y ) {
splay( u ) ; fr( u ) ^= true ;
Join( u , v ) ;
} else {
Access( v ) ; splay( v ) ; fr( v ) ^= true ;
Join( v , u ) ;
}
} else {
Cut( x ) ;
if ( Roof( u ) == x ) {
splay( u ) ; fr( u ) ^= true ;
Join( u , v ) ;
} else {
Access( v ) ; splay( v ) ; fr( v ) ^= true ;
Join( v , u ) ;
}
}
} else if ( ch == '*' ) {
int u , v ; ll c ; getint( u ) , getint( v ) , getll( c ) ;
Access( u ) ;
int lca = Access( v ) ;
splay( lca ) ; pushdown( lca ) ;
( V( lca ) *= c ) %= mod ;
sign( R( lca ) , c , 0 ) ;
update( lca ) ;
if ( lca != u ) {
splay( u ) ;
sign( u , c , 0 ) ;
}
} else {
int u , v ; getint( u ) , getint( v ) ;
Access( u ) ;
int lca = Access( v ) ;
splay( lca ) ; pushdown( lca ) ; pushdown( R( lca ) ) ;
ll ans = ( V( lca ) + sum( R( lca ) ) ) % mod ;
if ( lca != u ) {
splay( u ) ; pushdown( u ) ;
( ans += sum( u ) ) %= mod ;
}
putll( ans ) ;
}
}
return 0 ;
}
网友评论