题解
一个比较容易证明的结论是：这三个点必然会经过某一个点，并且该点到他们的距离相等。
这样，我们枚举每一个点，然后算一下每层深度有多少个这样的点，计数即可。
这样会有重复，不妨这么考虑：
一个点是“中心点”的前提是他是另外$3$个点的$LCA$。
所以为了避免某$2$个深度相同的点的$LCA$不是当前枚举的点，我们就把每一颗当前枚举点的子树看作是一个集合，集合中深度相同的$2$个点不可同时选取，就转化为了一个组合问题。
假设有$n$个集合，大小分别为要从其中$3$个集合中各选一个元素组成$3$元组个方案数显然是。这些方案数的和就是当前点的答案。然后考虑加入一个集合，要快速得到这个集合的贡献，就要维护其他集合两两乘积的和，把新集合大小乘上去就是新集合的贡献。维护两两乘积的和又需要维护所有集合大小之和，这就是代码里开了$f,g$2个数组的原因。$f$就是集合大小和，$g$就是两两乘积和。
这么做是$O(n^2)$的。
容易被卡。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,to[10005],nex[10005],at[10005]={0},cnt=0;
ll ans=0,f[5005],g[5005],d[5005]={0};
//次数1 2 3
void dfs(int cur,int fa,int de){
d[de]++;
for(int i=at[cur];i;i=nex[i])
if(to[i]!=fa)
dfs(to[i],cur,de+1);
}
void init(){
n=read();
int u,v;
for(int i=1;i<n;i++){
u=read(),v=read();
to[++cnt]=v,nex[cnt]=at[u],at[u]=cnt;
to[++cnt]=u,nex[cnt]=at[v],at[v]=cnt;
}
}
void solve(){
for(int i=1;i<=n;i++){
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int j=at[i];j;j=nex[j]){
dfs(to[j],i,1);
for(int k=1;k<=n;k++)//合并集合
ans+=d[k]*g[k],g[k]+=d[k]*f[k],f[k]+=d[k],d[k]=0;
}
}
printf("%lld\n",ans);
}
int main(){
init();
solve();
return 0;
}