10
14
2015
0

3522: [Poi2014]Hotel

3522: [Poi2014]Hotel

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 304  Solved: 156
[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

   因为是三个点之间距离相同。,。所以三个点不可能在一条链上。。只有可能为深度相同的点。。然后知道这点就可以DP了

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 5010;
struct data{ll x,y,next;} e[N<<1];
ll head[N],t1[N],t2[N],tmp[N],deep[N],Max,x,y,cnt,n,ans;
ll read(){
	ll x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
void Insert(ll x,ll y){
	e[++cnt].x = x;e[cnt].y = y;
	e[cnt].next = head[x];head[x] = cnt;
}
void dfs(ll x,ll fa){
	Max = max(Max,deep[x]);
	tmp[deep[x]]++;
	for (ll i=head[x];i;i=e[i].next)
		if (e[i].y!=fa) {deep[e[i].y] = deep[x]+1;dfs(e[i].y,x);}
}
int main(){
	n = read();
	for (ll i=1;i<n;i++){
		x = read();y = read();
		Insert(x,y);Insert(y,x);
	}
	for (ll x=1;x<=n;x++){
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		Max = 0;
		for (ll i=head[x];i;i=e[i].next){
			deep[e[i].y] = 1;
			dfs(e[i].y,x);
			for (ll j=1;j<=Max;j++){
				ans+=t2[j]*tmp[j];
				t2[j]+=t1[j]*tmp[j];
				t1[j]+=tmp[j];
			}
			for (ll j=1;j<=Max;j++) tmp[j] = 0;
		}
	}
	printf("%lld",ans);
}
Category: BZOJ题解 | Tags: | Read Count: 324

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com