BZOJ-3522: [Poi2014]Hotel（暴力）

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

枚举中间那个点，然后就暴力O（n^2）就好啦~

代码:

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

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

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

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

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

 

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

 

const int maxn = 5010 ;

const int maxm = 10100 ;

 

struct edge {

    edge *next ;

    int t ;

} E[ maxm ] ;

 

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

 

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 n ;

 

typedef long long ll ;

 

int d[ maxn ] , cnt[ maxn ] ;

ll dp[ 4 ][ maxn ] ;

 

void dfs( int now , int fa ) {

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

        d[ p -> t ] = d[ now ] + 1 ; dfs( p -> t , now ) ;

    }

}

 

void getd( int now , int fa ) {

    cnt[ d[ now ] ] ++ ;

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

}

 

int main(  ) {

    scanf( "%d" , &n ) ;

    memset( head , 0 , sizeof( head ) ) ;

    REP( i , 2 , n ) {

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

        addedge( s , t ) ;

    }

    ll ans = 0 ;

    rep( i , n ) {

        memset( dp , 0 , sizeof( dp ) ) ;

        rep( j , n ) dp[ 0 ][ j ] = 1 ;

        d[ i ] = 0 ;

        dfs( i , 0 ) ;

        travel( i ) {

            memset( cnt , 0 , sizeof( cnt ) ) ;

            getd( p -> t , i ) ;

            DOWN( j , 2 , 0 ) rep( k , n ) if ( dp[ j ][ k ] && cnt[ k ] ) {

                dp[ j + 1 ][ k ] += dp[ j ][ k ] * ll( cnt[ k ] ) ;

            }

        }

        rep( j , n ) ans += dp[ 3 ][ j ] ;

    }

    printf( "%lld\n" , ans ) ;

    return 0 ;

}