Example

Input

5
1 2
1 3
1 4
1 5


Output

6
#include <iostream>
#include <vector>
#include <map>
#include <functional>

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

using lint = long long;

constexpr lint MOD = 1000000009, B = 100007;

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

    Graph<> graph(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;

        graph[u].emplace_back(u, v);
        graph[v].emplace_back(v, u);
    }

    std::map<lint, lint> cnt;
    std::function<lint(int, int)>
        dfs = [&](int v, int p) {
            lint ret = 1;
            for (auto e : graph[v]) {
                if (e.dst == p) continue;
                (ret += dfs(e.dst, v) * B % MOD) %= MOD;
            }

            if (!cnt.count(ret)) cnt[ret] = 0;
            ++cnt[ret];

            return ret;
        };
    dfs(0, -1);

    lint ans = 0;
    for (auto p : cnt) {
        lint c = p.second;
        ans += c * (c - 1) / 2;
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}

