题意

给定一棵树，在树上选 3 个点，要求两两距离相等，求方案数。

$n\leq5000$ 。

题解

枚举中间点，设 $f_i,g_i,h_i$ 分别表示深度 $i$ 时扫过的子树中选 1、2 个点的方案数和当前子树选一个点的方案数。

代码

const int N = 5010;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
   	ll ans;
	int head[N], tot;
	struct Edge {
		int to, nxt;
	} e[N << 1];
	void add_edge (int u, int v) { e[++tot] = (Edge) {v, head[u]}, head[u] = tot; }
	ll f[N], g[N], h[N], mxdep;
	void dfs (int u, int fa, int dep) {
		mxdep = max(mxdep, 1ll * dep);
		h[dep]++;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to; if (v == fa) continue;
			dfs (v, u, dep + 1);
		}
	}
	int main () {
		n = Read();
		for (int i = 1; i < n; i++) { int u = Read(), v = Read(); add_edge (u, v); add_edge(v, u);}
		for (int u = 1; u <= n; u++) {
			memset (f, 0, sizeof f);
			memset (g, 0, sizeof g);
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				mxdep = 0;
				memset (h, 0, sizeof h);
				dfs (v, u, 1);
				for (int j = 1; j <= mxdep; j++) {
					ans += f[j] * h[j];
					f[j] += g[j] * h[j];
					g[j] += h[j];
				}
			}
		}
		printf ("%lld\n", ans);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}