标签：树，模拟
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
暴力枚举三个点的中心
依次对其子树暴力枚举
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;
}
