OI XXI - hot

// https://szkopul.edu.pl/problemset/problem/3_L6ZY7G-HX2CT7tYvkio8wH/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 5 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

std::vector<int> kra[sizik];

std::vector<int> z[sizik];

void DFS(int v, int p, int d, int j) {
    if ((int)z[j].size() < d) {
        z[j].push_back(1);
    } else {
        z[j][d - 1]++;
    }

    for (const auto& u : kra[v]) {
        if (u != p) {
            DFS(u, v, d + 1, j);
        }
    }
}

int q(int a) {
    return a * a;
}

void solve() {
    int n;
    std::cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        std::cin >> a >> b;

        kra[a].push_back(b);
        kra[b].push_back(a);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        _kra dodz, pref1, pref2;
        dodz.push_back({});
        pref1.push_back({0});
        pref2.push_back({0});

        for (int j = 1; j <= (int)kra[i].size(); j++) {
            z[j].clear();
            DFS(kra[i][j - 1], i, 1, j);

            for (int k = 0; k < (int)z[j].size(); k++) {
                while ((int)dodz.size() < k + 1) {
                    dodz.push_back({});
                    pref1.push_back({0});
                    pref2.push_back({0});
                }

                dodz[k].push_back(z[j][k]);
                pref1[k].push_back(z[j][k]);
                pref2[k].push_back(q(z[j][k]));
            }
        }

        for (auto& f : pref1) {
            for (int j = 1; j < (int)f.size(); j++) {
                f[j] += f[j - 1];
            }
        }

        for (auto& f : pref2) {
            for (int j = 1; j < (int)f.size(); j++) {
                f[j] += f[j - 1];
            }
        }

        for (int k = 0; k < (int)dodz.size(); k++) {
            for (int j = 0; j < (int)dodz[k].size(); j++) {
                int t = dodz[k][j] * (q(pref1[k][j]) - pref2[k][j]);
                ans += t;
            }
        }
    }

    ans /= 2;
    std::cout << ans << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}