题目描述

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

题目分析

n这么小那就随便搞了
注意到三个妹子一定是在一个点的三个儿子里 那就枚举每个点当根 令表示在i的子树里 距离i为j的点的个数 根据乘法原理搞一下就好了
但是发现这么做是O（n^2）的 发现第二维最大5000 那么开桶记录一下就可以了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int tot,head[5200],to[20200],net[20200];
void add(int x,int y) { net[++tot]=head[x],head[x]=tot,to[tot]=y;}
long long num[5200],su[5200],s[5200],ans;
int dep[20200],mx;
void dfs(int x,int temp)
{
    dep[x]=dep[temp]+1,num[dep[x]]++,mx=max(mx,dep[x]);
    for(int i=head[x];i;i=net[i])
        if(to[i]!=temp) dfs(to[i],x);
}
int main()
{
    scanf("%d",&n);
    for(int x,y,i=1;i<n;i++)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for(int i=1;i<=n;i++)
    {
        memset(s,0,sizeof s);
        memset(su,0,sizeof su);
        memset(dep,0,sizeof dep);
        mx=0;
        for(int j=head[i];j;j=net[j])
        {
            memset(num,0,sizeof num);
            dfs(to[j],i);
            for(int k=1;k<=mx;k++)
                ans+=su[k]*num[k],su[k]+=num[k]*s[k],s[k]+=num[k];
        }
    }
    printf("%lld",ans);
}