BZOJ-3589: 动态树（DFS序+线段树）

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

}