Bzoj3522 [poi2014]hotel

Posted by yjjr's blog on February 6, 2018

标签:树,模拟

Description

有一个树形结构的宾馆,n个房间,n-1条无向边,每条边的长度相同,任意两个房间可以相互到达。吉丽要给他的三个妹子各开(一个)房(间)。三个妹子住的房间要互不相同(否则要打起来了),为了让吉丽满意,你需要让三个房间两两距离相同。
有多少种方案能让吉丽满意?

Input

第一行一个数n
接下来n-1行,每行两个数x,y,表示xy之间有一条边相连。

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

 

暴力枚举三个点的中心

依次对其子树暴力枚举

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define reg(x) for(int i=head[x];i;i=e[i].next)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=5006;
LL deep[maxn],head[maxn],num[maxn],s1[maxn],s2[maxn],ans=0,cnt=0,n,mx;
struct edge{int to,next;}e[maxn<<1];

inline void dfs(int x,int fa)
{
	mx=max(mx,deep[x]);
	num[deep[x]]++;
	reg(x){
		if(e[i].to==fa)continue;
		deep[e[i].to]=deep[x]+1;
		dfs(e[i].to,x);
	}
}

int main()
{
	n=read();
	rep(i,1,n-1){
		int u=read(),v=read();
		e[++cnt]=(edge){u,head[v]};head[v]=cnt;
		e[++cnt]=(edge){v,head[u]};head[u]=cnt;
	}
	rep(x,1,n){
		mem(s1,0),mem(s2,0);
		reg(x){
			deep[e[i].to]=1;
			dfs(e[i].to,x);
			rep(j,1,mx){
				ans+=s2[j]*num[j];
				s2[j]+=num[j]*s1[j];
				s1[j]+=num[j];
			    num[j]=0;
			}
		}
	}
	printf("%lld\n",ans);
    return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr