传送门：【HDU】5002 Tree
题目分析：终于做出来啦~~~~
LCT模板题啊，不过还是很开心~
维护好set标记，add标记，flip标记，维护好最大值，第二大值，以及相应的出现次数就好了~
不过我的LCT效率不高，应该是更新的时候姿势不对，我再去优化优化~
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , n
const int MAXN = 100005 ;
const int INF = 0x3f3f3f3f ;
struct Node* null ;
struct Node {
Node* c[2] ;
Node* f ;
int size ;
int mmax ;
int smax ;
int mmax_num ;
int smax_num ;
int v ;
int flip ;
int addv ;
int setv ;
void newnode ( int val ) {
v = val ;
mmax = val ;
smax = -INF ;
mmax_num = 1 ;
smax_num = 0 ;
size = 1 ;
flip = 0 ;
addv = 0 ;
setv = -INF ;
f = c[0] = c[1] = null ;
}
void add_val ( int val ) {
if ( this == null ) return ;
addv += val ;
v += val ;
mmax += val ;
if ( smax != -INF ) smax += val ;
}
void set_val ( int val ) {
if ( this == null ) return ;
setv = val ;
addv = 0 ;
v = val ;
mmax = val ;
smax = -INF ;
mmax_num = size ;
smax_num = 0 ;
}
void reverse () {
if ( this == null ) return ;
swap ( c[0] , c[1] ) ;
flip ^= 1 ;
}
void push_up () {
size = c[0]->size + 1 + c[1]->size ;
int a[5] = { v , c[0]->mmax , c[1]->mmax , c[0]->smax , c[1]->smax } ;
sort ( a , a + 5 ) ;
int cnt = 0 ;
rep ( i , 1 , 5 ) if ( a[i] != a[cnt] ) a[++ cnt] = a[i] ;
mmax = a[cnt] ;
smax = a[cnt - 1] ;
mmax_num = smax_num = 0 ;
if ( v == mmax ) ++ mmax_num ;
if ( c[0]->mmax == mmax ) mmax_num += c[0]->mmax_num ;
if ( c[1]->mmax == mmax ) mmax_num += c[1]->mmax_num ;
if ( smax != -INF ) {
if ( v == smax ) ++ smax_num ;
if ( c[0]->mmax == smax ) smax_num += c[0]->mmax_num ;
if ( c[0]->smax == smax ) smax_num += c[0]->smax_num ;
if ( c[1]->mmax == smax ) smax_num += c[1]->mmax_num ;
if ( c[1]->smax == smax ) smax_num += c[1]->smax_num ;
}
}
void push_down () {
if ( flip ) {
c[0]->reverse () ;
c[1]->reverse () ;
flip = 0 ;
}
if ( setv != -INF ) {
c[0]->set_val ( setv ) ;
c[1]->set_val ( setv ) ;
setv = -INF ;
}
if ( addv ) {
c[0]->add_val ( addv ) ;
c[1]->add_val ( addv ) ;
addv = 0 ;
}
}
void link_child ( Node* o , int d ) {
c[d] = o ;
o->f = this ;
}
int is_root () {
return f == null || this != f->c[0] && this != f->c[1] ;
}
void sign_down () {
if ( !is_root () ) f->sign_down () ;
push_down () ;
}
void rotate ( int d ) {
Node* p = f ;
Node* gp = f->f ;
p->link_child ( c[d] , !d ) ;
if ( !p->is_root () ) {
if ( gp->c[0] == p ) gp->link_child ( this , 0 ) ;
else gp->link_child ( this , 1 ) ;
} else f = gp ;
link_child ( p , d ) ;
p->push_up () ;
}
void splay () {
sign_down () ;
while ( !is_root () ) {
if ( f->is_root () ) {
this == f->c[0] ? rotate ( 1 ) : rotate ( 0 ) ;
} else {
if ( f == f->f->c[0] ) {
this == f->c[0] ? f->rotate ( 1 ) : rotate ( 0 ) ;
rotate ( 1 ) ;
} else {
this == f->c[1] ? f->rotate ( 0 ) : rotate ( 1 ) ;
rotate ( 0 ) ;
}
}
}
push_up () ;
}
void access () {
Node* o = this ;
Node* x = null ;
while ( o != null ) {
o->splay () ;
o->link_child ( x , 1 ) ;
o->push_up () ;
x = o ;
o = o->f ;
}
splay () ;
}
void make_root () {
access () ;
reverse () ;
}
Node* find_root () {
access () ;
Node* o = this ;
while ( o->c[0] != null ) {
o->push_down () ;
o = o->c[0] ;
}
return o ;
}
void cut () {
access () ;
c[0]->f = null ;
c[0] = null ;
push_up () ;
}
void cut ( Node* o ) {
//if ( o == this || find_root () != o->find_root () ) return ;
o->make_root () ;
cut () ;
}
void link ( Node* o ) {
//if ( o == this || find_root () == o->find_root () ) return ;
o->make_root () ;
o->f = this ;
}
void add ( Node* o , int val ) {
//if ( find_root () != o->find_root () ) return ;
o->make_root () ;
access () ;
add_val ( val ) ;
}
void set ( Node* o , int val ) {
//if ( find_root () != o->find_root () ) return ;
o->make_root () ;
access () ;
set_val ( val ) ;
}
void query ( Node* o ) {
//if ( find_root () != o->find_root () ) return ;
o->make_root () ;
access () ;
if ( !smax_num ) printf ( "ALL SAME\n" ) ;
else printf ( "%d %d\n" , smax , smax_num ) ;
//printf ( "%d %d %d %d\n" , mmax , mmax_num , smax , smax_num ) ;
}
} ;
Node memory_pool[MAXN] ;
Node* cur ;
Node* node[MAXN] ;
int n , q ;
void clear () {
cur = memory_pool ;
cur->newnode ( -INF ) ;
null = cur ++ ;
null->size = 0 ;
}
void solve () {
int op , x , y , a , b , val ;
clear () ;
scanf ( "%d%d" , &n , &q ) ;
For ( i , 1 , n ) {
scanf ( "%d" , &val ) ;
cur->newnode ( val ) ;
node[i] = cur ++ ;
}
rep ( i , 1 , n ) {
scanf ( "%d%d" , &x , &y ) ;
node[x]->link ( node[y] ) ;
}
rep ( i , 0 , q ) {
scanf ( "%d%d%d" , &op , &x , &y ) ;
switch ( op ) {
case 1 :
scanf ( "%d%d" , &a , &b ) ;
node[x]->cut ( node[y] ) ;
node[a]->link ( node[b] ) ;
break ;
case 2 :
scanf ( "%d" , &val ) ;
node[x]->set ( node[y] , val ) ;
break ;
case 3 :
scanf ( "%d" , &val ) ;
node[x]->add ( node[y] , val ) ;
break ;
case 4 :
node[x]->query ( node[y] ) ;
break ;
default : break ;
}
}
}
int main () {
int T , cas = 0 ;
scanf ( "%d" , &T ) ;
while ( T -- ) {
printf ( "Case #%d:\n" , ++ cas ) ;
solve () ;
}
return 0 ;
}
-------Update 2014.09.28--------
优化了push_up，效率快了近一倍~
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , n
const int MAXN = 100005 ;
const int INF = 0x3f3f3f3f ;
struct Node* null ;
struct Node {
Node* c[2] ;
Node* f ;
int size ;
int mmax ;
int smax ;
int mmax_num ;
int smax_num ;
int v ;
int flip ;
int addv ;
int setv ;
void newnode ( int val ) {
v = val ;
mmax = val ;
smax = -INF ;
mmax_num = 1 ;
smax_num = 0 ;
size = 1 ;
flip = 0 ;
addv = 0 ;
setv = -INF ;
f = c[0] = c[1] = null ;
}
void add_val ( int val ) {
if ( this == null ) return ;
addv += val ;
v += val ;
mmax += val ;
if ( smax != -INF ) smax += val ;
}
void set_val ( int val ) {
if ( this == null ) return ;
setv = val ;
addv = 0 ;
v = val ;
mmax = val ;
smax = -INF ;
mmax_num = size ;
smax_num = 0 ;
}
void reverse () {
if ( this == null ) return ;
swap ( c[0] , c[1] ) ;
flip ^= 1 ;
}
void update ( int val , int num ) {
if ( val == -INF ) return ;
if ( val < smax ) return ;
if ( val > mmax ) {
smax = mmax ;
smax_num = mmax_num ;
mmax = val ;
mmax_num = num ;
} else if ( val == mmax ) {
mmax_num += num ;
} else if ( val > smax ) {
smax = val ;
smax_num = num ;
} else smax_num += num ;
}
void push_up () {
size = c[0]->size + 1 + c[1]->size ;
mmax = smax = -INF ;
mmax_num = smax_num = 0 ;
update ( v , 1 ) ;
update ( c[0]->mmax , c[0]->mmax_num ) ;
update ( c[0]->smax , c[0]->smax_num ) ;
update ( c[1]->mmax , c[1]->mmax_num ) ;
update ( c[1]->smax , c[1]->smax_num ) ;
}
void push_down () {
if ( flip ) {
c[0]->reverse () ;
c[1]->reverse () ;
flip = 0 ;
}
if ( setv != -INF ) {
c[0]->set_val ( setv ) ;
c[1]->set_val ( setv ) ;
setv = -INF ;
}
if ( addv ) {
c[0]->add_val ( addv ) ;
c[1]->add_val ( addv ) ;
addv = 0 ;
}
}
void link_child ( Node* o , int d ) {
c[d] = o ;
o->f = this ;
}
int is_root () {
return f == null || this != f->c[0] && this != f->c[1] ;
}
void sign_down () {
if ( !is_root () ) f->sign_down () ;
push_down () ;
}
void rotate ( int d ) {
Node* p = f ;
Node* gp = f->f ;
p->link_child ( c[d] , !d ) ;
if ( !p->is_root () ) {
if ( gp->c[0] == p ) gp->link_child ( this , 0 ) ;
else gp->link_child ( this , 1 ) ;
} else f = gp ;
link_child ( p , d ) ;
p->push_up () ;
}
void splay () {
sign_down () ;
while ( !is_root () ) {
if ( f->is_root () ) {
this == f->c[0] ? rotate ( 1 ) : rotate ( 0 ) ;
} else {
if ( f == f->f->c[0] ) {
this == f->c[0] ? f->rotate ( 1 ) : rotate ( 0 ) ;
rotate ( 1 ) ;
} else {
this == f->c[1] ? f->rotate ( 0 ) : rotate ( 1 ) ;
rotate ( 0 ) ;
}
}
}
push_up () ;
}
void access () {
Node* o = this ;
Node* x = null ;
while ( o != null ) {
o->splay () ;
o->link_child ( x , 1 ) ;
o->push_up () ;
x = o ;
o = o->f ;
}
splay () ;
}
void make_root () {
access () ;
reverse () ;
}
Node* find_root () {
access () ;
Node* o = this ;
while ( o->c[0] != null ) {
o->push_down () ;
o = o->c[0] ;
}
return o ;
}
void cut () {
access () ;
c[0]->f = null ;
c[0] = null ;
push_up () ;
}
void cut ( Node* o ) {
//if ( o == this || find_root () != o->find_root () ) return ;
o->make_root () ;
cut () ;
}
void link ( Node* o ) {
//if ( o == this || find_root () == o->find_root () ) return ;
o->make_root () ;
o->f = this ;
}
void add ( Node* o , int val ) {
//if ( find_root () != o->find_root () ) return ;
o->make_root () ;
access () ;
add_val ( val ) ;
}
void set ( Node* o , int val ) {
//if ( find_root () != o->find_root () ) return ;
o->make_root () ;
access () ;
set_val ( val ) ;
}
void query ( Node* o ) {
//if ( find_root () != o->find_root () ) return ;
o->make_root () ;
access () ;
if ( !smax_num ) printf ( "ALL SAME\n" ) ;
else printf ( "%d %d\n" , smax , smax_num ) ;
//printf ( "%d %d %d %d\n" , mmax , mmax_num , smax , smax_num ) ;
}
} ;
Node memory_pool[MAXN] ;
Node* cur ;
Node* node[MAXN] ;
int n , q ;
void clear () {
cur = memory_pool ;
cur->newnode ( -INF ) ;
null = cur ++ ;
null->size = 0 ;
}
void solve () {
int op , x , y , a , b , val ;
clear () ;
scanf ( "%d%d" , &n , &q ) ;
For ( i , 1 , n ) {
scanf ( "%d" , &val ) ;
cur->newnode ( val ) ;
node[i] = cur ++ ;
}
rep ( i , 1 , n ) {
scanf ( "%d%d" , &x , &y ) ;
node[x]->link ( node[y] ) ;
}
rep ( i , 0 , q ) {
scanf ( "%d%d%d" , &op , &x , &y ) ;
switch ( op ) {
case 1 :
scanf ( "%d%d" , &a , &b ) ;
node[x]->cut ( node[y] ) ;
node[a]->link ( node[b] ) ;
break ;
case 2 :
scanf ( "%d" , &val ) ;
node[x]->set ( node[y] , val ) ;
break ;
case 3 :
scanf ( "%d" , &val ) ;
node[x]->add ( node[y] , val ) ;
break ;
case 4 :
node[x]->query ( node[y] ) ;
break ;
default : break ;
}
}
}
int main () {
int T , cas = 0 ;
scanf ( "%d" , &T ) ;
while ( T -- ) {
printf ( "Case #%d:\n" , ++ cas ) ;
solve () ;
}
return 0 ;
}