hdu 5002 Tree (LCT)

几乎是模板题，维护一个最大值和次大值即可。

代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define ls son[0][rt]
#define rs son[1][rt]
using namespace std ;const int maxn = 100001 ;
const int INF = -1110011111 ;
int son[2][maxn] , mx[2][maxn] , cnt[2][maxn] , size[maxn] ;
int  fa[maxn] , is[maxn] , val[maxn] ;
int col[maxn] , add[maxn] , rev[maxn] ;
int st[55] ;
void push_up ( int rt ) {size[rt] = size[ls] + size[rs] + 1 ;st[1] = mx[0][ls] ;st[2] = mx[1][ls] ;st[3] = mx[0][rs] ;st[4] = mx[1][rs] ;st[5] = val[rt] ;sort ( st + 1 , st + 6 ) ;int T = unique ( st + 1 , st + 6 ) - st - 1 ;mx[0][rt] = st[T] , mx[1][rt] = st[T-1] ;cnt[0][rt] = cnt[1][rt] = 0 ;for ( int i = 0 ; i < 2 ; i ++ )for ( int j = 0 ; j < 2 ; j ++ ) {int v = mx[i][son[j][rt]] ;if ( v == mx[0][rt] ) cnt[0][rt] += cnt[i][son[j][rt]] ;if ( v == mx[1][rt] ) cnt[1][rt] += cnt[i][son[j][rt]] ;}if ( val[rt] == mx[0][rt] ) cnt[0][rt] ++ ;if ( val[rt] == mx[1][rt] ) cnt[1][rt] ++ ;
}void reverse ( int rt ) {if ( !rt ) return ;swap ( son[0][rt] , son[1][rt] ) ;rev[rt] ^= 1 ;
}void color ( int rt , int c ) {if ( !rt ) return ;val[rt] = c ;mx[0][rt] = col[rt] = c ;mx[1][rt] = add[rt] = INF ;cnt[0][rt] = size[rt] ;cnt[1][rt] = 0 ;
}void ADD ( int rt , int c ) {if ( !rt ) return ;if ( add[rt] == INF ) add[rt] = c ;else add[rt] += c ;mx[0][rt] += c ;val[rt] += c ;if ( mx[1][rt] != INF ) mx[1][rt] += c ;
}void push_down ( int rt ) {if ( rev[rt] ) {reverse ( ls ) ;reverse ( rs ) ;rev[rt] = 0 ;}if ( col[rt] != INF ) {color ( ls , col[rt] ) ;color ( rs , col[rt] ) ;col[rt] = INF ;}if ( add[rt] != INF ) {ADD ( ls , add[rt] ) ;ADD ( rs , add[rt] ) ;add[rt] = INF ;}
}void down ( int rt ) {if ( !is[rt] ) down ( fa[rt] ) ;push_down ( rt ) ;
}void rot ( int rt ) {int y = fa[rt] , z = fa[y] , c = rt == son[0][y] ;son[!c][y] = son[c][rt] ; fa[son[c][rt]] = y ;son[c][rt] = y ; fa[y] = rt ;fa[rt] = z ;if ( is[y] ) is[y] = 0 , is[rt] = 1 ;else son[y==son[1][z]][z] = rt ;push_up ( y ) ;
}void splay ( int rt ) {down ( rt ) ;while ( !is[rt] ) {int y = fa[rt] , z = fa[y] ;if ( !is[y] ) rot ( (rt==son[0][y]) == (y==son[0][z]) ? y : rt ) ;rot ( rt ) ;}push_up ( rt ) ;
}void access ( int rt ) {for ( int v = 0 ; rt ; rt = fa[rt] ) {splay ( rt ) ;is[rs] = 1 ; is[v] = 0 ;rs = v ;v = rt ;push_up ( rt ) ;}
}void change_root ( int rt ) {access ( rt ) ;splay ( rt ) ;reverse ( rt ) ;
}void cut ( int a , int b ) {change_root ( a ) ;access ( a ) ;splay ( b ) ;fa[b] = 0 ;
}void link ( int a , int b ) {change_root ( b ) ;fa[b] = a ;
}void gao1 ( int a , int b , int c , int d ) {cut ( a , b ) ;link ( c , d ) ;
}void gao2 ( int a , int b , int c ) {change_root ( a ) ;access ( b ) ;splay ( b ) ;color ( b , c ) ;
}void gao3 ( int a , int b , int c ) {change_root ( a ) ;access ( b ) ;splay ( b ) ;ADD ( b , c ) ;
}void print ( int rt ) {if ( !rt ) return ;printf ( "rt = %d , mx0 = %d , mx1 = %d\n" , rt , mx[0][rt] , mx[1][rt] ) ;print ( ls ) ;print ( rs ) ;
}
void gao4 ( int a , int b ) {change_root ( a ) ;access ( b ) ;splay ( b ) ;//   print ( b ) ;if ( mx[1][b] == INF ) puts ( "ALL SAME" ) ;else printf ( "%d %d\n" , mx[1][b] , cnt[1][b] ) ;
}void init ( int rt ) {int a ;scanf ( "%d" , &a ) ;val[rt] = mx[0][rt] = a ;mx[1][rt] = INF ;cnt[0][rt] = 1 ;cnt[1][rt] = 0 ;size[rt] = 1 ;add[rt] = col[rt] = INF ;son[0][rt] = son[1][rt] = fa[rt] = rev[rt] = 0 ;is[rt] = 1 ;
}int main () {int T , ca = 0 ;int n , m ;
//    freopen ( "main.in" , "r" , stdin ) ;mx[0][0] = mx[1][0] = INF ;is[0] = 1 , fa[0] = 0 ;scanf ( "%d" , &T ) ;while ( T -- ) {scanf ( "%d%d" , &n , &m ) ;for ( int i = 1 ; i <= n ; i ++ )init ( i ) ;for ( int i = 1 ; i < n ; i ++ ) {int a , b ;scanf ( "%d%d" , &a , &b ) ;link ( a , b ) ;}printf ( "Case #%d:\n" , ++ ca ) ;for ( int i = 1 ; i <= m ; i ++ ) {int a , b , c , d ;scanf ( "%d" , &c ) ;if ( c == 1 ) {int f ;scanf ( "%d%d%d%d" , &a , &b , &d , &f ) ;if ( a == b || d == f ) continue ;gao1 ( a , b , d , f ) ;} else if ( c == 2 ) {scanf ( "%d%d%d" , &a , &b , &d ) ;gao2 ( a , b , d ) ;} else if ( c == 3 ) {scanf ( "%d%d%d" , &a , &b , &d ) ;gao3 ( a , b , d ) ;} else {scanf ( "%d%d" , &a , &b ) ;gao4 ( a , b ) ;}}}
}
/*
2
3 2
1 1 2
1 2
1 3
4 2 3
*/