Реши задачу на c++ Байтландия имеет очень развитую...

Имеем дерево из N станций (так как N вершин и N-1 перегонов, связно). Маршрут между a и b единственный, и в задаче маршруты ориентированные (пример с 2→3 и 3→2 считает оба).

Нужны все маршруты с нечётным числом вершин на пути, то есть с чётным расстоянием по рёбрам dist(a,b) (потому что |path| = dist + 1).

Характеристика = медиана номеров вершин на пути (после сортировки). Так как все номера уникальны, это просто k-й по величине номер на пути, где
k = (|path|+1)/2 = (dist+2)/2.

Значит задача сводится к большому числу запросов вида: k-я статистика на пути в дереве.

Идея решения

Сделаем:

1. LCA (двоичное поднятие), чтобы быстро получать расстояние и разложение пути.
2. Персистентное сегментное дерево частот по значениям 1..N для каждого узла v: хранит мультимножество номеров вершин на пути root → v.
   Тогда мультимножество значений на пути u–v:

$$T(u)+T(v)-T(lca)-T(parent(lca))$$

3. По этим 4 версиям сегдерева находим k-й минимум за O(log N).

Перебираем все пары u<v, если dist чётно — находим медиану и прибавляем +2 (оба направления u→v и v→u).

Сложность:
O(N log N + N^2 log N), при N=4000 это нормально.

---

C++ (полное решение)

cpp
#include <bits/stdc++.h>
using namespace std;

struct PSTNode {
    int l = 0, r = 0;
    int sum = 0;
};

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

    int N;
    cin >> N;
    vector<vector<int>> g(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (N == 1) {
        cout << 0 << "\n";
        return 0;
    }

    int LOG = 1;
    while ((1 << LOG) <= N) LOG++;
    vector<vector<int>> up(LOG, vector<int>(N + 1, 0));
    vector<int> depth(N + 1, 0);

    // Персистентное сегдерево
    vector<PSTNode> seg;
    seg.reserve(N * 20);
    seg.push_back(PSTNode()); // нулевой узел

    auto sumNode = [&](int idx) -> int {
        return idx ? seg[idx].sum : 0;
    };

    function<int(int,int,int,int)> update = [&](int prev, int l, int r, int pos) -> int {
        int cur = (int)seg.size();
        seg.push_back(seg[prev]);
        seg[cur].sum++;
        if (l != r) {
            int mid = (l + r) >> 1;
            if (pos <= mid) seg[cur].l = update(seg[prev].l, l, mid, pos);
            else seg[cur].r = update(seg[prev].r, mid + 1, r, pos);
        }
        return cur;
    };

    vector<int> ver(N + 1, 0); // версия сегдерева для каждого узла

    // DFS итеративно: строим parent, depth и версии сегдерева
    vector<int> parent(N + 1, 0);
    vector<int> st;
    st.reserve(N);
    st.push_back(1);
    parent[1] = 0;
    depth[1] = 0;
    ver[1] = update(0, 1, N, 1);

    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        up[0][v] = parent[v];

        for (int to : g[v]) {
            if (to == parent[v]) continue;
            parent[to] = v;
            depth[to] = depth[v] + 1;
            ver[to] = update(ver[v], 1, N, to); // добавляем значение = номер вершины
            st.push_back(to);
        }
    }

    // binary lifting
    for (int i = 1; i < LOG; i++) {
        for (int v = 1; v <= N; v++) {
            int p = up[i - 1][v];
            up[i][v] = p ? up[i - 1][p] : 0;
        }
    }

    auto lca = [&](int a, int b) -> int {
        if (depth[a] < depth[b]) swap(a, b);
        int diff = depth[a] - depth[b];
        for (int i = 0; i < LOG; i++) {
            if (diff & (1 << i)) a = up[i][a];
        }
        if (a == b) return a;
        for (int i = LOG - 1; i >= 0; i--) {
            if (up[i][a] != up[i][b]) {
                a = up[i][a];
                b = up[i][b];
            }
        }
        return up[0][a];
    };

    // k-th smallest по 4 версиям (a+b-c-d)
    auto kth = [&](int A, int B, int C, int D, int k) -> int {
        int l = 1, r = N;
        while (l != r) {
            int mid = (l + r) >> 1;
            int AL = A ? seg[A].l : 0;
            int BL = B ? seg[B].l : 0;
            int CL = C ? seg[C].l : 0;
            int DL = D ? seg[D].l : 0;

            int leftCount = sumNode(AL) + sumNode(BL) - sumNode(CL) - sumNode(DL);
            if (k <= leftCount) {
                A = AL; B = BL; C = CL; D = DL;
                r = mid;
            } else {
                k -= leftCount;
                A = A ? seg[A].r : 0;
                B = B ? seg[B].r : 0;
                C = C ? seg[C].r : 0;
                D = D ? seg[D].r : 0;
                l = mid + 1;
            }
        }
        return l;
    };

    vector<long long> ans(N + 1, 0);

    for (int u = 1; u <= N; u++) {
        for (int v = u + 1; v <= N; v++) {
            int w = lca(u, v);
            int dist = depth[u] + depth[v] - 2 * depth[w];
            if (dist % 2 != 0) continue; // нужен нечётный размер пути => dist чётно

            int len = dist + 1;
            int k = (len + 1) / 2; // медиана = k-й по величине
            int pw = up[0][w];     // parent(lca) или 0

            int med = kth(ver[u], ver[v], ver[w], pw ? ver[pw] : 0, k);
            ans[med] += 2; // оба направления маршрута
        }
    }

    for (int i = 1; i <= N; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Если хочешь — могу также дать версию с небольшими микрооптимизациями (чтобы гарантированно уложиться по времени на самых жёстких лимитах), но для N=4000 этот вариант обычно проходит уверенно.