3522: [Poi2014]Hotel( 樹形dp )

枚舉中點x( 即選出的三個點 a , b , c 滿足 dist( x , a ) = dist( x , b ) = dist( x , c ) ) , 然后以 x 為 root 做 dfs , 顯然兩個位于 x 的同一顆子樹內的點是不可能被同時選到的 . 我們對 x 的每一顆子樹進行 dfs , 記錄下當前子樹中的點到 x 距離為 d ( 1 <= d <= n ) 有多少個 , 記為 cnt[ 0 ][ i ] . 然后 cnt[ 1 ][ i ] 記錄之前 dfs 過的子樹的 cnt[ 0 ][ i ] 之和 , cnt[ 2 ][ i ] 記錄之前 dfs 過的子樹中任意兩顆不同子樹中的cnt[ 0 ][ i ] * cnt[ 0 ][ i ] 之和 . cnt[ ?][ i ] 的計算看代碼

----------------------------------------------------------------------------

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream>

#define clr( x , c ) memset( x , c , sizeof( x ) )

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

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

using namespace std;

typedef long long ll;

const int maxn = 5000 + 5;

ll cnt[ 3 ][ maxn ];

int n;

struct edge {

int to;

edge* next;

} E[ maxn << 1 ] , *pt = E , *head[ maxn ];

inline void add_edge( int u , int v ) {

pt -> to = v;

pt -> next = head[ u ];

head[ u ] = pt++;

pt -> to = u;

pt -> next = head[ v ];

head[ v ] = pt++;

}

int dfs( int x , int fa , int d ) {

cnt[ 0 ][ d++ ]++;

REP( x ) if( e -> to != fa )?

? ?dfs( e -> to , x , d );

}

void work() {

ll ans = 0;

rep( i , n ) {

clr( cnt[ 1 ] , 0 );

clr( cnt[ 2 ] , 0 );

REP( i ) {

clr( cnt[ 0 ] , 0 );

dfs( e -> to , i , 1 );

rep( i , n ) {

ans += cnt[ 0 ][ i ] * cnt[ 2 ][ i ];

cnt[ 2 ][ i ] += cnt[ 0 ][ i ] * cnt[ 1 ][ i ];

cnt[ 1 ][ i ] += cnt[ 0 ][ i ];

}

}

}

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

}

void init() {

clr( head , 0 );

cin >> n;

rep( i , n - 1 ) {

int u , v , d;

scanf( "%d%d" , &u , &v );

add_edge( --u , --v );

}

}

int main() {

freopen( "test.in" , "r" , stdin );

init();

work();

? ? return 0;?

}?

??

----------------------------------------------------------------------------?

3522: [Poi2014]Hotel

Time Limit:?20 Sec??Memory Limit:?128 MB
Submit:?273??Solved:?132
[Submit][Status][Discuss]

Description

有一個樹形結構的賓館，n個房間，n-1條無向邊，每條邊的長度相同，任意兩個房間可以相互到達。吉麗要給他的三個妹子各開（一個）房（間）。三個妹子住的房間要互不相同（否則要打起來了），為了讓吉麗滿意，你需要讓三個房間兩兩距離相同。
有多少種方案能讓吉麗滿意？

Input

第一行一個數n。
接下來n-1行，每行兩個數x,y，表示x和y之間有一條邊相連。

Output

讓吉麗滿意的方案數。

Sample Input

7
1 2
5 7
2 5
2 3
5 6
4 5

Sample Output

5

HINT

【樣例解釋】

{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

【數據范圍】

n≤5000

Source

By Dzy

?