RT，想不明白哪里空间开大了。

PS：

1. 尝试过改成链式前向星存图，还是 MLE；
2. 用的是第一篇题解的思路，先树形dp求环上每个点子树内的直径，再单调对列求经过环的直径。

#include <bits/stdc++.h>
using i64 = long long;

struct Edge {
    int to;
    i64 w;
};

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

    int n;
    std::cin >> n;
    std::vector<std::vector<int>> adj(n + 1);
    std::vector<Edge> e;

    auto addEdge = [&](int u, int v, int w) {
        adj[u].push_back(e.size());
        e.push_back({v, w});
    };

    for (int i = 1; i <= n; i++) {
        int v, w;
        std::cin >> v >> w;
        addEdge(i, v, w);
        addEdge(v, i, w);
    }

    std::vector<bool> vis(n + 1), incircle(n + 1);
    std::vector<int> from(n + 1), circle;

    std::function<void(int, int)> dfs1 = [&](int u, int fromid) {
        vis[u] = 1;
        for (int i : adj[u]) {
            auto [v, w] = e[i];
            if ((i ^ 1) == fromid || incircle[v]) {
                continue;
            }
            if (vis[v]) {
                incircle[v] = true;
                int cur = u;
                circle.push_back(v);
                while (cur != v) {
                    incircle[cur] = true;
                    circle.push_back(cur);
                    cur = from[cur];
                }
            } else {
                from[v] = u;
                dfs1(v, i);
            }
        }
    };

    std::vector<std::array<i64, 2>> dp(n + 1);

    std::function<void(int, int)> dfs2 = [&](int u, int from) {
        for (int i : adj[u]) {
            auto [v, w] = e[i];
            if ((i ^ 1) == from || incircle[v]) {
                continue;
            }
            dfs2(v, u);
            if (dp[v][0] + w > dp[u][0]) {
                dp[u][1] = dp[u][0];
                dp[u][0] = dp[v][0] + w;
            } else {
                dp[u][1] = std::max(dp[u][1], dp[v][0] + w);
            }
        }
    };

    i64 ans = 0;

    for (int u = 1; u <= n; u++) {
        if (!vis[u]) {
            circle.clear();
            dfs1(u, -1);

            int m = circle.size();
            circle.push_back(circle.front());
            i64 res = 0;

            std::vector<i64> d(m * 2 + 2), f(m * 2 + 1);

            for (int i = 0; i < m; i++) {
                int x = circle[i];
                dfs2(x, -1);
                res = std::max(res, dp[x][0] + dp[x][1]);
                f[i + 1] = f[i + 1 + m] = dp[x][0];
                i64 w = 0;  // 注意可能有重边
                for (int y : adj[x]) {
                    if (e[y].to == circle[i + 1]) {
                        w = std::max(w, e[y].w);
                    }
                }
                d[i + 2] = d[i + 2 + m] = w;
            }

            for (int i = 2; i <= m * 2; i++) {
                d[i] += d[i - 1];
            }

            // // 求最大的 f[i]+f[j]+d[j]-d[i]，要求 0<i-j<m。经典单调队列的应用。
            std::deque<int> que;
            auto g = [&](int p) -> i64 {
                return f[p] - d[p];
            };

            for (int i = 1; i <= m * 2; i++) {
                while (que.size() && que.front() <= i - m) {
                    que.pop_front();
                }
                while (que.size() && g(que.back()) < g(i)) {
                    que.pop_back();
                }
                if (que.size()) {
                    res = std::max(res, g(que.front()) + f[i] + d[i]);
                }
                que.push_back(i);
            }
            ans += res;
        }
    }

    std::cout << ans;

    return 0;
}