a.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

int calc_cnt_vertex(int x, int pr = -1){
    int cnt_vertex = 1;
    for (int to : g[x]){
        if (to != pr && !removed[to]){
           cnt[to] = calc_cnt_vertex(to, x);
           cnt_vertex += cnt[to];
        }
    }
    return cnt_vertex;
}

int find_centroid(int x, int n, int pr = -1){

    for (int to : g[x]){
        if (to != pr && !removed[to]){
            if (cnt[to] * 2 > n)
                return find_centroid(to, n, x);
        }
    }
    return x;
}
void find_dist(int x, int h, int pr = -1){
    dist[x] = h;
    answer += all_dists[d - h];
    for (int to : g[x]){
        if (to != pr && !removed[to]){
           find_dist(to, h + 1, x);
        }
    }
}

void add_dist(int x, int pr = -1){
    all_dists[dist[x]]++;
    for (int to : g[x]){
        if (to != pr && !removed[to]){
           add_dist(to, x);
        }
    }
}

void calc_ans(int x){
    for (int i = 0; i <= cnt[x]; i++){
        all_dist[i] = 0;
    }
    for (int to : g[x]){
        if (!removed[to]){
            find_dist(to, 1);
            add_dist(to);
        }
    }
}

void calc(int x, int lvl_centroid){
    cnt[x] = calc_cnt_vertex(x);
    int v = find_centroid(x, cnt[x]);

    removed[v] = true;
    calc_ans(v);

    for (int to : g[v]){
        if (!removed[to]){
            calc(to, lvl_centroid + 1);
        }
    }
}

int main(){
    IOS;
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    calc(1, 1);

}