注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-3083: 遥远的国度(树链剖分+线段树)  

2014-02-13 14:08:00|  分类: 线段树,树链剖分, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目: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 ;

  • }



  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018