题解
暴力做法，不会长链剖分。
任取一个点作为根，设这三个点为 (u,v,w) 且 (dep_uge dep_vge dep_w)，那么 (u,v,w) 到 (operatorname{lca}(u,v)) 的距离需要相等。
枚举这个 (operatorname{lca}=r)，并将其设为根。设 (r) 的儿子是 (s_1,s_2,dots,s_k)，那么就是取三个点使得它们深度相同，并且它们所在的 (s) 不同的方案数。于是直接 bfs 即可。
代码写得比较丑陋。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T>
void Read(T &_x){
_x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
_x*=_f;
}
template<typename T,typename... Args>
void Read(T &_x,Args& ...others){
Read(_x);Read(others...);
}
typedef long long ll;
const int N=5005;
int n,dep[N],fa[N],cnt[N],bel[N];
vector<int> e[N];
ll f[N][4];
int main(){
Read(n);
For(i,1,n-1){
int u,v;
Read(u,v);
e[u].push_back(v),e[v].push_back(u);
}
ll ans=0;
For(root,1,n){
int cur=1,tot=0;
dep[root]=fa[root]=0;
queue<int> q;map<int,int> mp;
for(int u:e[root]) q.push(u),bel[u]=u,fa[u]=root;
while(!q.empty()){
int u=q.front();q.pop();
dep[u]=dep[fa[u]]+1;
if(dep[u]>1) bel[u]=bel[fa[u]];
if(dep[u]==cur+1){
f[1][0]=1,f[1][1]=cnt[1],f[1][2]=f[1][3]=0;
For(i,2,tot){
f[i][0]=1;
For(j,1,3) f[i][j]=1LL*cnt[i]*f[i-1][j-1]+f[i-1][j];
}
ans+=f[tot][3];
++cur;
For(i,1,tot) cnt[i]=0;
mp.clear();tot=0;
}
int num;
if(mp.count(bel[u])) num=mp.at(bel[u]);
else mp.insert({bel[u],num=++tot});
++cnt[num];
for(int v:e[u]) if(v!=fa[u]){
fa[v]=u,q.push(v);
}
}
f[1][0]=1,f[1][1]=cnt[1],f[1][2]=f[1][3]=0;
For(i,2,tot){
f[i][0]=1;
For(j,1,3) f[i][j]=1LL*cnt[i]*f[i-1][j-1]+f[i-1][j];
}
ans+=f[tot][3];
For(i,1,tot) cnt[i]=0;
}
printf("%lld
",ans);
return 0;
}