[文章目录]
Description
有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开一个房间。三个妹子住的房间要互不相同，为了让吉丽满意，你需要让三个房间两两距离相同。有多少种方案能让吉丽满意？n<=5000
枚举中间点，搜索整颗树。每搜索一个不同的儿子之后枚举深度，统计答案。f[i]记录深度为i选一个节点的方案数，g[i]记录深度为i选两个不同节点的方案数，推一下即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll num[5100],f[5100],g[5100],ans;
int head[5100],to[10100],nxt[10100],cnt,n;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x,int pre,int dfn)
{
num[dfn]++;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs(to[i],x,dfn+1);
}
int main()
{
scanf("%d",&n);
int x,y;
for(int i=1;i!=n;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for(int i=1;i<=n;++i)
{
memset(f,0,sizeof f);
memset(g,0,sizeof g);
for(int j=head[i];j;j=nxt[j])
{
dfs(to[j],i,1);
for(int k=1;num[k];++k)
{
ans+=num[k]*g[k];
g[k]+=f[k]*num[k];
f[k]+=num[k];
num[k]=0;
}
}
}
printf("%lld\n",ans);
return 0;
}