题意

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

n≤5000

题解

(⊙o⊙)…还有一个加强版，等会做。。估计会在下一篇见到他吧。。
这个的话，显然$n^2$可以做呀
考虑到如果我们要每一个节点做根
然后统计答案，就在他三个不同的子树里面选择三个深度一样的点，这个东西用乘法原理搞就可以了
我是怎么想的呢？其实是对拍调着调着弄出来的TAT
一开始是这么想的
我们让1为根
然后枚举每一个点i，让他为最深的点
然后考虑枚举一个剩下两个点LCA
然后乘法原理搞一下
然后发现还有“LCA”在上面的没有考虑。。
然后搞了很久
发现这些都等价于枚举了一个“LCA”，然后在LCA的三个子树里面找
然后就做完了

CODE:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long LL;
using namespace std;
const int N=5005;
struct qq
{int x,y,last;
}e[N*2];int num,last[N];
int n;
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
int f[N],f1[N],f2[N];
int dep[N];
void dfs (int x,int fa)
{f[dep[x]]++;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==fa) continue;dep[y]=dep[x]+1;dfs(y,x);}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d",&n);for (int u=1;u<n;u++){int x,y;scanf("%d%d",&x,&y);init(x,y);init(y,x);}LL ans=0;for (int u=1;u<=n;u++){memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));for (int i=last[u];i!=-1;i=e[i].last){int y=e[i].y;dep[y]=1;dfs(y,u);for (int j=1;j<=n;j++){ans=ans+f2[j]*f[j];f2[j]=f2[j]+f1[j]*f[j];f1[j]=f1[j]+f[j];}memset(f,0,sizeof(f));}}printf("%lld",ans);return 0;
}