Para cualesquiera tres nodos $a$, $b$ y $c$, los tres caminos $a \rightarrow b$, $b \rightarrow c$ y $c \rightarrow a$ tienen un único nodo en común.

Sea $r$ el nodo común mencionado. La terna $(a, b, c)$ es buena si y solo si las longitudes de los caminos $r \rightarrow a$, $r \rightarrow b$ y $r \rightarrow c$ son iguales.

Video de YouTube (abT6JItO6b8)

¿Crees que tienes una solución $\mathcal{O}(N^3)$ que no implica recorrer todas las ternas de nodos? Si es así, ¿es realmente $\mathcal{O}(N^3)$ o es en realidad $\mathcal{O}(N^2)$ amortizado?

Explicación

Como $N$ es pequeño, podemos calcular el número de ternas buenas con nodo común $r$, para todo $r$ de 1 a $N$.

Para algún $r$, enraizamos el árbol en $r$. Luego podemos hacer DFS para hallar las profundidades de los subárboles de los hijos de $r$, y la cantidad de nodos a cada profundidad en cada subárbol. Sea \texttt{at\\_depth}_i[d] la cantidad de nodos a profundidad $d$ en el subárbol del hijo $i$.

Cada nodo de una terna buena debe estar a la misma profundidad y en subárboles distintos, así que la cantidad de ternas buenas que aporta la profundidad $d$ del subárbol $i$ es:

Podemos recorrer cada par válido $(i, d)$ en tiempo $\mathcal{O}(N)$ amortizado, ya que cada par corresponde a al menos un nodo del árbol.

¿Pero cómo calcular \sum_{j < i}\texttt{at\\_depth}_j[d] y \sum_{j > i}\texttt{at\\_depth}_j[d] rápidamente?

Nótese que solo tenemos que calcular una de estas sumas, y que se parecen mucho a sumas de prefijos/sufijos. En mi solución, calculo \sum_{j > i}\texttt{at\\_depth}_j[d] usando sumas de sufijos. Llamemos a este valor $\texttt{after}_i[d]$.

Como solo nos importan los $\texttt{after}_i[d]$ de los pares válidos $(i, d)$, podemos mantener un arreglo global que guarde los valores máximos de $\texttt{after}_i[d]$ hasta el momento (con todos los elementos en 0 al inicio). Esto nos permite calcular todos los $\texttt{after}_i[d]$ interesantes en tiempo $\mathcal{O}(N)$.

Como alternativa, podemos ordenar los hijos de $r$ por sus profundidades y luego calcular $\texttt{after}_i[d]$ de forma directa, lo cual sigue siendo lo bastante rápido para pasar.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[5001];
 
void find_dep(int node, int parent, pair<int, vector<int>> &root, int depth = 0) {
	if (depth == root.first) {
		root.first++;
		root.second.push_back(1);
	} else root.second[depth]++;
	for (int i : graph[node])
		if (i != parent) find_dep(i, node, root, depth + 1);
}
 
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
 
	if (n < 4) {
		printf("0\n");
		return 0;
	}
 
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		int m = graph[i].size();
		vector<pair<int, vector<int>>> dep(m);
		vector<vector<int>> aft(m);
		for (int j = 0; j < m; j++) find_dep(graph[i][j], i, dep[j]);
		vector<int> tot(max_element(dep.begin(), dep.end())->first, 0);
 
		for (int j = m - 1; ~j; j--) {
			aft[j].resize(dep[j].first);
			for (int k = 0; k < dep[j].first; k++) {
				aft[j][k] = tot[k];
				tot[k] += dep[j].second[k];
			}
		}
 
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < dep[j].first; k++) {
				ans += (tot[k] - dep[j].second[k] - aft[j][k]) * dep[j].second[k] *
				       aft[j][k];
			}
		}
	}
 
	printf("%lld\n", ans);
	return 0;
}

Hay que usar std::vectors para garantizar memoria $\mathcal{O}(N)$.