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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3589: 动态树(DFS序+线段树)  

2014-05-16 21:33:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3589


其实这题可以不用链剖的额,直接上DFS序就可以维护了。然后暴力容斥一下,对于路径的并就用几个LCA分类一下,然后大概就没什么了,细节倒是挺多的。


代码:


  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  •  

  • using namespace std ;

  •  

  • #define travel( x ) for ( vector < int > :: iterator p = E[ x ].begin(  ) ; p != E[ x ].end(  ) ; ++ p )

  • #define addedge( s , t ) add( s , t ) , add( t , s )

  • #define add( s , t ) E[ s ].push_back( t )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  •  

  • #define right( t ) ( left( t ) ^ 1 )

  • #define left( t ) ( t << 1 )

  • #define L( t ) sgt[ t ].l

  • #define R( t ) sgt[ t ].r

  • #define S( t ) sgt[ t ].sum

  • #define D( t ) sgt[ t ].delta

  • #define I( t ) sgt[ t ].num_in

  • #define O( t ) sgt[ t ].num_out

  •  

  • typedef long long ll ;

  •  

  • ll mod = ll( 1 ) << 31 ;

  •  

  • const int maxn = 201000 ;

  •  

  • vector < int > E[ maxn ] ;

  •  

  • int n , in[ maxn ] , out[ maxn ] , arr[ maxn << 1 ] , h[ maxn ] , cnt = 0 , up[ maxn ][ 21 ] ;

  •  

  • void dfs( int now , int fa ) {

  •     arr[ in[ now ] = ++ cnt ] = now ;

  •     travel( now ) if ( *p != fa ) {

  •         up[ *p ][ 0 ] = now , h[ *p ] = h[ now ] + 1 ;

  •         dfs( *p , now ) ;

  •     }

  •     arr[ out[ now ] = ++ cnt ] = - now ;

  • }

  •  

  • int lca( int u , int v ) {

  •     if ( ( ! u ) || ( ! v ) ) return 0 ;

  •     if ( h[ u ] < h[ v ] ) swap( u , v ) ;

  •     for ( int i = 20 ; i >= 0 ; -- i ) if ( h[ up[ u ][ i ] ] >= h[ v ] ) u = up[ u ][ i ] ;

  •     if ( v == u ) return u ;

  •     for ( int i = 20 ; i >= 0 ; -- i ) if ( up[ v ][ i ] != up[ u ][ i ] ) {

  •         v = up[ v ][ i ] , u = up[ u ][ i ] ;

  •     }

  •     return up[ v ][ 0 ] ;

  • }

  •  

  • struct node {

  •     int l , r ;

  •     ll delta , sum , num_in , num_out ;

  •     node(  ) {

  •         delta = sum = num_in = num_out = 0 ;

  •     }

  • } sgt[ maxn << 3 ] ;

  •  

  • void build( int l , int r , int t ) {

  •     L( t ) = l , R( t ) = r ;

  •     if ( l == r ) {

  •         if ( arr[ l ] > 0 ) I( t ) = 1 ; else O( t ) = 1 ;

  •         return ;

  •     }

  •     int mid = ( l + r ) >> 1 ;

  •     build( l , mid , left( t ) ) , build( mid + 1 , r , right( t ) ) ;

  •     I( t ) = I( left( t ) ) + I( right( t ) ) , O( t ) = O( left( t ) ) + O( right( t ) ) ;

  • }

  •  

  • void pushdown( int t ) {

  •     if ( t && D( t ) ) {

  •         ( S( t ) += D( t ) * I( t ) ) %= mod ;

  •         S( t ) = ( S( t ) - ( ( D( t ) * O( t ) ) % mod ) + mod ) % mod ;

  •         if ( L( t ) < R( t ) ) {

  •             ( D( left( t ) ) += D( t ) ) %= mod , ( D( right( t ) ) += D( t ) ) %= mod ;

  •         }

  •         D( t ) = 0 ;

  •     }

  • }

  •  

  • void update( int t ) {

  •     pushdown( t ) ;

  •     pushdown( left( t ) ) , pushdown( right( t ) ) ;

  •     S( t ) = ( S( left( t ) ) + S( right( t ) ) ) % mod ;

  • }

  •  

  • void change( int l , int r , ll d , int t ) {

  •     pushdown( t ) ;

  •     if ( l == L( t ) && r == R( t ) ) {

  •         D( t ) += d ;

  •         pushdown( t ) ;

  •         return ;

  •     }

  •     int mid = ( L( t ) + R( t ) ) >> 1 ;

  •     if ( r <= mid ) change( l , r , d , left( t ) ) ; else

  •     if ( l > mid ) change( l , r , d , right( t ) ) ; else

  •     change( l , mid , d , left( t ) ) , change( mid + 1 , r , d , right( t ) ) ;

  •     update( t ) ;

  • }

  •  

  • ll query( int l , int r , int t ) {

  •     if ( l > r ) return 0 ;

  •     pushdown( t ) ;

  •     if ( l == L( t ) && r == R( t ) ) return S( t ) ;

  •     int mid = ( L( t ) + R( t ) ) >> 1 ;

  •     if ( r <= mid ) return query( l , r , left( t ) ) ;

  •     if ( l > mid ) return query( l , r , right( t ) ) ;

  •     return ( query( l , mid , left( t ) ) + query( mid + 1 , r , right( t ) ) ) % mod ;

  • }

  •  

  • struct edge {

  •     int u , v ;

  • } q[ 10 ] ;

  •  

  • edge operator + ( edge x , edge y ) {

  •     if ( h[ x.u ] > h[ y.u ] ) swap( x , y ) ;

  •     if ( h[ x.v ] < h[ y.u ] ) return ( edge ) { 0 , 0 } ;

  •     int a = lca( x.u , y.u ) , b = lca( x.v , y.u ) ;

  •     if ( a == x.u && b == y.u ) {

  •         int c = lca( x.v , y.v ) ;

  •         return ( edge ) { y.u , c } ;

  •     }

  •     return ( edge ) { 0 , 0 } ;

  • }

  •  

  • ll temp = 0 ;

  •  

  • ll Query( edge e ) {

  •     return query( in[ e.u ] , in[ e.v ] , 1 ) ;

  • }

  •  

  • int m , k ;

  •  

  • void DFS( int now , ll state , edge y ) {

  •     if ( ! y.u && ! y.v ) return ;

  •     if ( now == k ) {

  •         if ( y.u == - 1 ) return ;

  •         temp = ( temp + state * Query( y ) + mod ) % mod ;

  •         return ;

  •     }

  •     DFS( now + 1 , state , y ) ;

  •     edge x = ( y.u == - 1 ) ? q[ now ] : q[ now ] + y ;

  •     DFS( now + 1 , - state , x ) ;

  • }

  •  

  • void test( int t ) {

  •     pushdown( t ) ;

  •     printf( "[ %d , %d ] -: %lld\n" , L( t ) , R( t ) , S( t ) ) ;

  •     if ( L( t ) < R( t ) ) {

  •         test( left( t ) ) , test( right( t ) ) ;

  •     }

  • }

  •  

  • int main(  ) {

  •     scanf( "%d" , &n ) ;

  •     rep( i , ( n - 1 ) ) {

  •         int s , t ; scanf( "%d%d" , &s , &t ) ;

  •         addedge( s , t ) ;

  •     }

  •     h[ 1 ] = 1 , memset( up , 0 , sizeof( up ) ) ;

  •     memset( in , 0 , sizeof( in ) ) , memset( out , 0 , sizeof( out ) ) ;

  •     dfs( 1 , 0 ) ;

  •     for ( int i = 1 ; i <= 20 ; ++ i ) for ( int j = 0 ; j ++ < n ; ) {

  •         up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;

  •     }

  •     build( 1 , n << 1 , 1 ) ;

  •     scanf( "%d" , &m ) ;

  •     while ( m -- ) {

  •         int x ; scanf( "%d" , &x ) ;

  •         if ( ! x ) {

  •             int v ; ll d ; scanf( "%d%lld" , &v , &d ) ;

  •             change( in[ v ] , out[ v ] , d , 1 ) ;

  •         } else {

  •             scanf( "%d" , &k ) ;

  •             for ( int i = 0 ; i < k ; ++ i ) {

  •                 scanf( "%d%d" , &q[ i ].u , &q[ i ].v ) ;

  •                 if ( h[ q[ i ].u ] > h[ q[ i ].v ] ) swap( q[ i ].v , q[ i ].u ) ;

  •             }

  •             temp = 0 ;

  •             DFS( 0 , - 1 , ( edge ){ - 1 , - 1 } ) ;

  •             printf( "%lld\n" , temp ) ;

  •         }

  •     }

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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