BZOJ-2819: Nim（BIT+LCA+DFS序列）

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

刚开始还以为是神马博弈论的神题，仔细一看原来只是维护一下树上链的sg函数，说白了就是维护一下链的xor和，那就直接用DFS序列+BIT水过去就可以啦~（LCA当然也要顺便求一下）

代码（懒得写倍增，就只写写了TarjanLCA了，BZOJ上面是linux真好，不会爆栈~~）：

c8177f3e6709c93d08537f999d3df8dcd100543e.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 1000100
#define lowbit( x ) ( ( - x ) & x )
#define AddEdge( s , t ) Add( s , t ) , Add( t , s )
#define INSERT( u , v , t ) Insert( u , v , t ) , Insert( v , u , t )
 
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 , lca[ MAXN ] , father[ MAXN ] , in[ MAXN ] , out[ MAXN ] , cnt = 0 ;
bool f[ MAXN ] ;
 
int Find( int x ) {
    int i = x , j = x ; for ( ; father[ i ] ; i = father[ i ] ) ;
    while ( father[ j ] ) {
        int k = father[ j ] ; father[ j ] = i ; j = k ;
    }
    return i ;
}
 
struct qtype {
    int v , t ;
    qtype *next ;
} *qhead[ MAXN ] ;
 
void Insert( int u , int v , int t ) {
    qtype *p = new( qtype ) ;
    p -> v = v , p -> t = t , p -> next = qhead[ u ] ;
    qhead[ u ] = p ;
}
 
void dfs( int v ) {
    in[ v ] = ++ cnt , f[ v ] = false ;
    for ( qtype *p = qhead[ v ] ; p ; p = p -> next ) if ( ! f[ p -> v ] ) lca[ p -> t ] = Find( p -> v ) ;
    for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
        dfs( p -> t ) ; father[ Find( p -> t ) ] = v ; 
    }
    out[ v ] = ++ cnt ;
}
 
int bit[ MAXN ] ;
 
void Bit_add( int x , int y ) {
    for ( ; x <= cnt ; x += lowbit( x ) ) bit[ x ] ^= y ;
}
 
int Bit_sum( int x ) {
    int rec = 0 ; for ( ; x ; x -= lowbit( x ) ) rec ^= bit[ x ] ; return rec ;
}
 
int query[ MAXN ][ 3 ] , q , value[ MAXN ] ;
 
int main(  ) {
    memset( head , 0 , sizeof( head ) ) , memset( qhead , 0 , sizeof( qhead ) ) ;
    scanf( "%d" , &n ) ; for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , &value[ i ] ) ;
    for ( int i = 0 ; i ++ < n - 1 ; ) {
        int s , t ; scanf( "%d%d" , &s , &t ) ; AddEdge( s , t ) ;
    }
    scanf( "%d" , &q ) ; for ( int i = 0 ; i ++ < q ; ) {
        int ch ; for ( ch = getchar(  ) ; ch != 'Q' && ch != 'C' ; ch = getchar(  ) ) ;
        query[ i ][ 0 ] = ch != 'Q' ;
        scanf( "%d%d" , &query[ i ][ 1 ] , &query[ i ][ 2 ] ) ;
        if ( ! query[ i ][ 0 ] ) INSERT( query[ i ][ 1 ] , query[ i ][ 2 ] , i ) ;
    }
    memset( bit , 0 , sizeof( bit ) ) ; 
    memset( f , true , sizeof( f ) ) ;
    memset( father , 0 , sizeof( father ) ) ;
    dfs( 1 ) ;
    for ( int i = 0 ; i ++ < n ; ) Bit_add( in[ i ] , value[ i ] ) , Bit_add( out[ i ] , value[ i ] ) ;
    for ( int i = 0 ; i ++ < q ; ) if ( ! query[ i ][ 0 ] ) {
        printf( ( Bit_sum( in[ query[ i ][ 1 ] ] ) ^ Bit_sum( in[ query[ i ][ 2 ] ] ) ^ value[ lca[ i ] ] ) == 0 ? "No\n" : "Yes\n" ) ;
    } else {
        Bit_add( in[ query[ i ][ 1 ] ] , value[ query[ i ][ 1 ] ] ^ query[ i ][ 2 ] ) ;
        Bit_add( out[ query[ i ][ 1 ] ] , value[ query[ i ][ 1 ] ] ^ query[ i ][ 2 ] ) ;
        value[ query[ i ][ 1 ] ] = query[ i ][ 2 ] ;
    }
    return 0 ;
}