Реши на c++ Задача D. Маршруты Красной поляны Имя ...

Граф связный, вершин N и рёбер тоже N ⇒ это унициклический граф (ровно один простой цикл).
Любой путь вне цикла лежит в деревьях, подвешенных к вершинам цикла, а неоднозначность кратчайшего пути возможна только из-за цикла (максимум 2 кратчайших пути — по двум направлениям, когда вершины “напротив” в чётном цикле).

Нужно:

1. найти диаметр D (максимальное кратчайшее расстояние),
2. посчитать сумму количества кратчайших путей по всем парам вершин на расстоянии D.

Ниже — решение за O(N).

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

struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline char read() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

    template <class T>
    bool nextInt(T &out) {
        char c;
        do { c = read(); if (!c) return false; } while (c <= ' ');
        bool neg = false;
        if (c == '-') { neg = true; c = read(); }
        long long val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        out = neg ? -val : val;
        return true;
    }
};

struct Edge { int to, next; };

static const int MAXN = 200000;
static const int OFF  = MAXN + 2;

int main() {
    FastScanner fs;
    int N;
    if (!fs.nextInt(N)) return 0;

    vector<int> head(N + 1, -1);
    vector<Edge> edges(2 * N);
    int ec = 0;
    vector<int> deg(N + 1, 0);

    auto addEdge = [&](int u, int v) {
        edges[ec] = {v, head[u]}; head[u] = ec++;
        edges[ec] = {u, head[v]}; head[v] = ec++;
        deg[u]++; deg[v]++;
    };

    for (int i = 0; i < N; i++) {
        int u, v;
        fs.nextInt(u); fs.nextInt(v);
        addEdge(u, v);
    }

    // 1) Находим вершины цикла (обрезка листьев)
    vector<char> isCycle(N + 1, 1);
    deque<int> q;
    for (int v = 1; v <= N; v++) if (deg[v] == 1) q.push_back(v);

    while (!q.empty()) {
        int v = q.front(); q.pop_front();
        isCycle[v] = 0;
        for (int e = head[v]; e != -1; e = edges[e].next) {
            int u = edges[e].to;
            if (isCycle[u]) {
                if (--deg[u] == 1) q.push_back(u);
            }
        }
    }

    // 2) Восстанавливаем порядок вершин на цикле
    int start = -1;
    for (int v = 1; v <= N; v++) if (isCycle[v]) { start = v; break; }

    vector<int> cycle;
    cycle.reserve(N);
    int prev = -1, cur = start;
    do {
        cycle.push_back(cur);
        int nxt = -1;
        for (int e = head[cur]; e != -1; e = edges[e].next) {
            int u = edges[e].to;
            if (isCycle[u] && u != prev) { nxt = u; break; }
        }
        prev = cur;
        cur = nxt;
    } while (cur != start);

    int m = (int)cycle.size();

    // 3) Для каждого корня на цикле считаем:
    //    - downDepth[root] = максимальная глубина в подвешенном дереве (0 если нет)
    //    - downCnt[root]   = количество вершин на этой глубине
    //    - diamTree[root]  = диаметр внутри подвешенного дерева
    //    - waysTree[root]  = число пар вершин на этом диаметре (в дереве путь единственный)
    vector<int> parent(N + 1, -2);
    vector<int> downDepth(N + 1, 0);
    vector<long long> downCnt(N + 1, 1);
    vector<int> compDiamLen(N + 1, 0);
    vector<long long> compWays(N + 1, 0);

    int Dtree = 0;

    vector<int> order; order.reserve(1024);
    vector<int> st;    st.reserve(1024);

    for (int idx = 0; idx < m; idx++) {
        int root = cycle[idx];

        order.clear();
        st.clear();
        st.push_back(root);
        parent[root] = -1;

        // Обход компоненты: запрещаем переходы по ребрам цикла (cycle-cycle)
        while (!st.empty()) {
            int v = st.back(); st.pop_back();
            order.push_back(v);
            for (int e = head[v]; e != -1; e = edges[e].next) {
                int u = edges[e].to;
                if (isCycle[v] && isCycle[u]) continue;
                if (u == parent[v]) continue;
                parent[u] = v;
                st.push_back(u);
            }
        }

        int bestLen = 0;
        long long bestWays = 0;

        // DP снизу вверх по order (в обратном порядке)
        for (int t = (int)order.size() - 1; t >= 0; --t) {
            int v = order[t];

            // Ветвь "сама вершина v" как лист: глубина 0, количество 1
            int bestDepth = 0;
            long long total = 1;
            long long sumsq = 1;
            int sources = 1;

            int secondDepth = -1;
            long long secondTotal = 0;

            for (int e = head[v]; e != -1; e = edges[e].next) {
                int u = edges[e].to;
                if (isCycle[v] && isCycle[u]) continue;
                if (parent[u] == v) {
                    int d = downDepth[u] + 1;
                    long long c = downCnt[u];

                    if (d > bestDepth) {
                        secondDepth = bestDepth;
                        secondTotal = total;

                        bestDepth = d;
                        total = c;
                        sumsq = c * c;
                        sources = 1;
                    } else if (d == bestDepth) {
                        total += c;
                        sumsq += c * c;
                        sources++;
                    } else if (d > secondDepth) {
                        secondDepth = d;
                        secondTotal = c;
                    } else if (d == secondDepth) {
                        secondTotal += c;
                    }
                }
            }

            downDepth[v] = bestDepth;
            downCnt[v] = total;

            // Кандидат диаметра через v
            int candLen = -1;
            long long candWays = 0;

            if (sources >= 2) {
                candLen = 2 * bestDepth;
                candWays = (total * total - sumsq) / 2; // пары из разных ветвей максимальной глубины
            } else if (secondDepth >= 0) {
                candLen = bestDepth + secondDepth;
                candWays = total * secondTotal;
            }

            if (candWays > 0) {
                if (candLen > bestLen) {
                    bestLen = candLen;
                    bestWays = candWays;
                } else if (candLen == bestLen) {
                    bestWays += candWays;
                }
            }
        }

        compDiamLen[root] = bestLen;
        compWays[root] = bestWays;
        Dtree = max(Dtree, bestLen);
    }

    // массивы по циклу
    vector<int> w(m);
    vector<long long> cnt(m);
    for (int i = 0; i < m; i++) {
        int v = cycle[i];
        w[i] = downDepth[v];
        cnt[i] = downCnt[v];
    }

    // 4) Диаметр с использованием цикла:
    // максимум w[i] + w[j] + dist_cycle(i,j)
    auto max_window = [&](int k) -> int {
        if (k <= 0) return INT_MIN / 4;
        deque<int> dq; // индексы i, (w[i]-i) по убыванию
        int best = INT_MIN / 4;
        int limit = (m - 1) + k;

        for (int j = 1; j <= limit; j++) {
            int i = j - 1;
            if (i < m) {
                int val = w[i] - i;
                while (!dq.empty()) {
                    int bi = dq.back();
                    if (w[bi] - bi <= val) dq.pop_back();
                    else break;
                }
                dq.push_back(i);
            }
            int lb = j - k;
            while (!dq.empty() && dq.front() < lb) dq.pop_front();

            if (!dq.empty()) {
                int ii = dq.front();
                int cand = (w[ii] - ii) + w[j % m] + j; // (w[ii]+w[j]+(j-ii))
                best = max(best, cand);
            }
        }
        return best;
    };

    int Dcycle;
    if (m & 1) {
        int L = m / 2;
        Dcycle = max_window(L);
    } else {
        int L = m / 2;
        int best1 = max_window(L - 1);          // dist < L
        int best2 = INT_MIN / 4;                // противоположные (dist = L)
        for (int i = 0; i < L; i++)
            best2 = max(best2, w[i] + w[i + L] + L);
        Dcycle = max(best1, best2);
    }

    int D = max(Dtree, Dcycle);

    long long ans = 0;

    // 5) Добавляем вклад из диаметров внутри деревьев (там путь всегда 1)
    if (D == Dtree) {
        for (int i = 0; i < m; i++) {
            int root = cycle[i];
            if (compDiamLen[root] == D) ans += compWays[root];
        }
    }

    // Подсчет числа пар на цикле с dist <= k (уникальный кратчайший путь по циклу)
    auto ways_window = [&](int Dval, int k) -> long long {
        if (k <= 0) return 0LL;
        vector<long long> freq(2 * MAXN + 5, 0LL); // по ключу (w[i]-i) -> сумма cnt[i]
        long long ways = 0;
        int limit = (m - 1) + k;

        for (int j = 0; j <= limit; j++) {
            if (j > 0) {
                int i = j - 1;
                if (i < m) {
                    int key = w[i] - i;
                    if (key >= -MAXN && key <= MAXN) freq[key + OFF] += cnt[i];
                }
            }
            int rem = j - k - 1;
            if (rem >= 0 && rem < m) {
                int key = w[rem] - rem;
                if (key >= -MAXN && key <= MAXN) freq[key + OFF] -= cnt[rem];
            }

            if (j == 0) continue;
            int t = j % m;
            int target = Dval - (w[t] + j);
            if (target < -MAXN || target > MAXN) continue;

            ways += cnt[t] * freq[target + OFF];
        }
        return ways;
    };

    // 6) Добавляем вклад диаметров, проходящих через цикл
    if (D == Dcycle) {
        if (m & 1) {
            int L = m / 2;
            ans += ways_window(D, L); // все пары учитываются один раз
        } else {
            int L = m / 2;
            ans += ways_window(D, L - 1); // dist < L: путь по циклу единственный
            // противоположные вершины: 2 кратчайших пути по циклу
            for (int i = 0; i < L; i++) {
                if (w[i] + w[i + L] + L == D) {
                    ans += cnt[i] * cnt[i + L] * 2LL;
                }
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}

Если хочешь — могу коротко пояснить на конкретном примере из условия, как именно считаются w[i], cnt[i] и почему в чётном цикле появляется множитель 2.