![3522: [Poi2014]Hotel( 树形dp )](/default/index/img?u=aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhBdmFXMWhaMlZ6TUM1amJtSnNiMmR6TG1OdmJTOWliRzluTWpBeE5TODNNak00T1RZdk1qQXhOVEEzTHpFek1UazBNREV3TURjNU5UZ3pOQzV3Ym1jPS5qcGc= "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