BZOJ-3631: [JLOI2014]松鼠的新家(LCA)

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

裸裸的求个LCA，然后树上前缀和维护一下就好啦~

代码（倍增+DFS似乎有点慢，其实这题可以完全O（n）的额）：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

 

const int maxn = 301000 ;

const int maxm = maxn << 1 ;

 

struct edge {

    edge *next ;

    int t ;

} E[ maxm ] ;

 

edge *pt = E , *head[ maxn ] ;

 

#define Init_edge memset( head , 0 , sizeof( head ) ) ;

 

inline void add( int s , int t ) {

    pt -> t = t , pt -> next = head[ s ] ; head[ s ] = pt ++ ;

}

 

inline void addedge( int s , int t ) {

    add( s , t ) , add( t , s ) ;

}

 

int up[ maxn ][ 21 ] , a[ maxn ] , n , h[ maxn ] ;

 

#define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )

 

void getfa( int now , int fa ) {

    up[ now ][ 0 ] = fa , h[ now ] = h[ fa ] + 1 ;

    travel( now ) if ( p -> t != fa ) getfa( p -> t , now ) ;

}

 

#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

 

inline int getlca( int v , int u ) {

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

    DOWN( i , 20 , 0 ) if ( h[ up[ v ][ i ] ] >= h[ u ] ) v = up[ v ][ i ] ;

    if ( v == u ) return v ;

    DOWN( i , 20 , 0 ) if ( up[ v ][ i ] != up[ u ][ i ] ) {

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

    }

    return up[ v ][ 0 ] ;

}

 

int sm[ maxn ] ;

 

void getsm( int now , int fa ) {

    travel( now ) if ( p -> t != fa ) {

        getsm( p -> t , now ) ; sm[ now ] += sm[ p -> t ] ;

    }

}

 

int main(  ) {

    scanf( "%d" , &n ) ;

    REP( i , 1 , n ) scanf( "%d" , a + i ) ;

    Init_edge ;

    REP( i , 2 , n ) {

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

    }

    h[ 0 ] = 0 ; getfa( 1 , 0 ) ;

    REP( i , 1 , 20 ) REP( j , 1 , n ) up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;

    memset( sm , 0 , sizeof( sm ) ) ;

    REP( i , 2 , n ) {

        int lca = getlca( a[ i - 1 ] , a[ i ] ) ;

        sm[ a[ i - 1 ] ] ++ , sm[ a[ i ] ] ++ , sm[ lca ] -- , sm[ up[ lca ][ 0 ] ] -- ;

    }

    getsm( 1 , 0 ) ;

    REP( i , 1 , n ) printf( "%d\n" , sm[ i ] - ( i != a[ 1 ] ) ) ;

    return 0 ;

}