BZOJ-3083: 遥远的国度（树链剖分+线段树）
2018-11-13 本文已影响0人
AmadeusChan
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3083
树链剖分弄出来的那个序列也是DFS序列，然后就SGT维护一下，对于换根分类讨论一下就可以了。（突然想通sone1怎么写了。。。好开心~）
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define AddEdge( s , t ) Add( s , t ) , Add( t , s )
#define MAXN 100010
#define MAXB 20
#define left( t ) ( t << 1 )
#define right( t ) ( left( t ) ^ 1 )
#define ll long long
const ll inf = ( ll )( 0x7fffffff ) * ( ll )( 0x7fffffff ) ;
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 , roof , up[ MAXN ][ MAXB + 1 ] , B , h[ MAXN ] , beg[ MAXN ] ;
ll w[ MAXN ] ;
bool f[ MAXN ] ;
int arr[ MAXN ] , in[ MAXN ] , out[ MAXN ] , cnt = 0 , size[ MAXN ] , child[ MAXN ] ;
void dfs0( int v ) {
f[ v ] = false , size[ v ] = 1 , child[ v ] = 0 ;
int ret = 0 ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
h[ p -> t ] = h[ v ] + 1 , up[ p -> t ][ 0 ] = v ;
dfs0( p -> t ) ;
if ( size[ p -> t ] > ret ) {
ret = size[ p -> t ] , child[ v ] = p -> t ;
}
size[ v ] += size[ p -> t ] ;
}
}
void dfs1( int v , int u ) {
f[ v ] = false , arr[ in[ v ] = ++ cnt ] = v , beg[ v ] = u ;
if ( child[ v ] ) {
dfs1( child[ v ] , u ) ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
dfs1( p -> t , p -> t ) ;
}
}
out[ v ] = cnt ;
}
struct node {
int l , r ;
ll Min , flag ;
node( ) {
flag = 0 ;
}
} sgt[ MAXN << 3 ] ;
void pushdown( int t ) {
if ( sgt[ t ].flag ) {
sgt[ t ].Min = sgt[ t ].flag ;
if ( sgt[ t ].l < sgt[ t ].r ) {
sgt[ left( t ) ].flag = sgt[ right( t ) ].flag = sgt[ t ].flag ;
}
sgt[ t ].flag = 0 ;
}
}
void update( int t ) {
pushdown( t ) ;
if ( sgt[ t ].l < sgt[ t ].r ) {
pushdown( left( t ) ) , pushdown( right( t ) ) ;
sgt[ t ].Min = min( sgt[ left( t ) ].Min , sgt[ right( t ) ].Min ) ;
}
}
void build( int l , int r , int t ) {
sgt[ t ].l = l , sgt[ t ].r = r ;
if ( l == r ) {
sgt[ t ].Min = w[ arr[ l ] ] ; return ;
}
int mid = ( l + r ) >> 1 ;
build( l , mid , left( t ) ) , build( mid + 1 , r , right( t ) ) ;
update( t ) ;
}
void change( int l , int r , ll v , int t ) {
pushdown( t ) ;
if ( sgt[ t ].l == l && sgt[ t ].r == r ) {
sgt[ t ].flag = v ; pushdown( t ) ;
return ;
}
int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;
if ( r <= mid ) change( l , r , v , left( t ) ) ; else
if ( l > mid ) change( l , r , v , right( t ) ) ; else {
change( l , mid , v , left( t ) ) , change( mid + 1 , r , v , right( t ) ) ;
}
update( t ) ;
}
ll query( int l , int r , int t ) {
pushdown( t ) ;
if ( l == sgt[ t ].l && r == sgt[ t ].r ) return sgt[ t ].Min ;
int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;
if ( r <= mid ) return query( l , r , left( t ) ) ;
if ( l > mid ) return query( l , r , right( t ) ) ;
return min( query( l , mid , left( t ) ) , query( mid + 1 , r , right( t ) ) ) ;
}
int Lca( int u , int v ) {
if ( h[ u ] < h[ v ] ) swap( u , v ) ;
for ( int i = MAXB ; i >= 0 ; -- i ) {
if ( h[ up[ u ][ i ] ] >= h[ v ] ) {
u = up[ u ][ i ] ;
}
}
if ( u == v ) return u ;
for ( int i = MAXB ; i >= 0 ; -- i ) {
if ( up[ u ][ i ] != up[ v ][ i ] ) {
u = up[ u ][ i ] , v = up[ v ][ i ] ;
}
}
return up[ v ][ 0 ] ;
}
void Change( int v , int u , ll c ) {
while ( h[ v ] >= h[ u ] ) {
if ( h[ beg[ v ] ] > h[ u ] ) {
change( in[ beg[ v ] ] , in[ v ] , c , 1 ) ;
v = up[ beg[ v ] ][ 0 ] ;
} else {
change( in[ u ] , in[ v ] , c , 1 ) ;
break ;
}
}
}
ll Solve( int v ) {
if ( v == roof ) return query( 1 , n , 1 ) ;
int lca = Lca( v , roof ) ;
if ( lca == v ) {
ll ret = inf ;
int t = roof ;
for ( int i = MAXB ; i >= 0 ; -- i ) if ( h[ up[ t ][ i ] ] > h[ v ] ) {
t = up[ t ][ i ] ;
}
if ( in[ t ] - 1 ) ret = min( ret , query( 1 , in[ t ] - 1 , 1 ) ) ;
if ( out[ t ] < n ) ret = min( ret , query( out[ t ] + 1 , n , 1 ) ) ;
return ret ;
} else return query( in[ v ] , out[ v ] , 1 ) ;
}
int main( ) {
memset( head , 0 , sizeof( head ) ) ;
scanf( "%d%d" , &n , &m ) ;
for ( int i = 1 ; i < n ; ++ i ) {
int s , t ; scanf( "%d%d" , &s , &t ) ;
AddEdge( s , t ) ;
}
for ( int i = 0 ; i ++ < n ; ) scanf( "%lld" , w + i ) ;
scanf( "%d" , &roof ) ;
memset( f , true , sizeof( f ) ) ;
h[ 1 ] = 1 ;
dfs0( 1 ) ;
memset( f , true , sizeof( f ) ) ;
dfs1( 1 , 1 ) ;
for ( int i = 0 ; i ++ < MAXB ; ) {
for ( int j = 0 ; j ++ < n ; ) {
up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;
}
}
build( 1 , n , 1 ) ;
while ( m -- ) {
int x , v , u , lca ;
ll c ;
scanf( "%d" , &x ) ;
switch ( x ) {
case 1 :
scanf( "%d" , &v ) ;
roof = v ;
break ;
case 2 :
scanf( "%d%d%lld" , &u , &v , &c ) ;
lca = Lca( u , v ) ;
Change( u , lca , c ) , Change( v , lca , c ) ;
break ;
case 3 :
scanf( "%d" , &v ) ;
printf( "%lld\n" , Solve( v ) ) ;
break ;
}
}
return 0 ;
}
