Description：

有一个树形结构，求选 $3$ 个点两两距离相等有多少种方案。

$1\leqslant n\leqslant5000$

Solution：

设 $k$ 为离三个点距离相等的点，那么这三个点一定在 $k$ 的三个不同子树中，那么就可以用换根 $DP$ 求出到每个点长度为 $l$ 的点的个数，这个可以到每个点时把他的某个儿子的贡献去掉，最后在加回来，这样对某个儿子统计答案时就不用考虑父子关系了，然后统计答案就只用开两个变量一个个子树转移即可。

注意不要在递归里使用全局变量，不然进入子树后会被修改回来之后就不对了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 5010

typedef long long ll;

int f[MAXN][MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool v[MAXN];

#define R register

int dep[MAXN];

void dp1(int k)

{

	v[k] = true;

	f[k][0] = 1;

	for(R int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp1(e[i].to);

		dep[k] = max(dep[k],dep[e[i].to] + 1);

		for(R int j = 1;j <= dep[k];++j)f[k][j] += f[e[i].to][j - 1];

	}

	v[k] = false;

	return;

}

ll ans = 0;

inline ll calc(int k)

{

	R ll res = 0;

	for(R int l = 1;l <= n;++l)

	{

		R ll tmp1 = 0,tmp2 = 0;

		f[k][l] = 0;

		for(R int i = lin[k];i != 0;i = e[i].nxt)

		{

			f[k][l] += f[e[i].to][l - 1];

			res += tmp2 * f[e[i].to][l - 1];

			tmp2 += tmp1 * f[e[i].to][l - 1];

			tmp1 += f[e[i].to][l - 1];

		}

	}

	return res;

}

void dp2(int k)

{

	v[k] = true;

	ans += calc(k);

	for(R int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		for(R int j = 1;j <= n;++j)f[k][j] -= f[e[i].to][j - 1];

		dp2(e[i].to);

		for(R int j = n;j >= 2;--j)f[k][j] += f[e[i].to][j - 1] - f[k][j - 2];

		f[k][1] += f[e[i].to][0];

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(R int i = 1;i < n;++i)add(rd(),rd());

	dp1(1);

	dp2(1);

	cout << ans << endl;

	return 0;

}