题目描述：
给定一棵树，在树上选 \(3\) 个点，要求两两距离相等，求方案数。
数据范围：
\(1\le n\le 5000\)
\(1\le a,b\le n\)
思路：
一开始我想的就是枚举两个点，然后处理第三个点。
但是发现这样做非常的不正确，并且非常容易算重，所以我舍去了这种方式。
但是在想这种做法的时候，我们会发现，如果想要使得三个点距离相同，就等于需要找到两个点的路径中点，然后这个中点与三个点的距离相同。
然后我们又又又发现一件事情，如果这个中点被当成了根，显然现在我们选择的三个点只需要深度相同，距离肯定就都相同了。
所以我们不妨枚举这个中点是哪一个点，我们假设这个点为 \(a\)
然后我们以 \(a\) 为根，所有 \(a\) 的子树中每个子树内最多只能有一个被选择的节点，因为如果超过一个，显然 \(lca\) 就不是 \(a\) 了。
问题转换为在同一深度的节点中，每颗子树内最多选择一个节点且一共选择三个节点的方案数。
然后我们思考这个问题怎么处理？
首先我们令 \(f_i\) 表示在遍历当前这棵子树之前的所有子树中，在深度 \(i\) 选择两个点的方案数是多少；\(g_i\) 表示在遍历当前这棵子树之前的所有子树中，在深度 \(i\) 选择一个点的方案数是多少；\(cnt_i\) 表示当前这棵子树深度为 \(i\) 的数量
可以较为轻松的推出转移方程：
\(ans\leftarrow f_i\times cnt_i\)
\(f_i\leftarrow g_i\times cnt_i\)
\(g_i\leftarrow cnt_i\)
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5005;
const int inf=0x3f3f3f3f;
int n;
vector<int>G[maxn];
int cnt[maxn],f[maxn],g[maxn];
int mxdep;
void dfs(int u,int f,int dep){
cnt[dep]++;
mxdep=max(mxdep,dep);
for(int v:G[u]){
if(v==f)continue;
dfs(v,u,dep+1);
}
}
void init(){
for(int i=1;i<=n;i++)f[i]=g[i]=0;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<n;i++){
int u,v;
scanf("%lld%lld",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
int ans=0;
for(int i=1;i<=n;i++){
init();
for(int j:G[i]){
for(int _=1;_<=n;_++)cnt[_]=0;
mxdep=-inf;
dfs(j,i,1);
for(int k=1;k<=mxdep;k++){
ans+=f[k]*cnt[k];
f[k]+=g[k]*cnt[k];
g[k]+=cnt[k];
}
}
}
printf("%lld\n",ans);
return 0;
}