开2e6

开1e6+1e5

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6;
struct node
{
    int x, y;
    long long w;
};
vector<node> EDGE;
bool cmp(node a, node b)
{
    if (a.x != b.x)
        return a.x < b.x;
    else if (a.y != b.y)
        return a.y < b.y;
    else
        return a.w > b.w;
}
struct edge
{
    int next, to;
    long long w;
} e[N << 1];
int head[N], cnt;
void add(int f, int t, long long v)
{
    e[++cnt] = edge{head[f], t, v};
    head[f] = cnt;
}
int n;
long long maxn, ans;
int st[N], c[N], tail, tot, vis[N];
long long sum[N];
long long d[N], DIS[N];
vector<int> SCC[N], CB[N];
long long dp(int u, int f)
{
    long long max1 = 0, max2 = 0;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == f || c[v] == 2)
            continue;

        long long sl = dp(v, u) + e[i].w;
        if (sl > max1)
            max2 = max1, max1 = sl;
        else if (sl > max2)
            max2 = sl;
    }
    maxn = max(maxn, max1 + max2);
    return max1;
}
void get_CB(int u, int f)
{
    CB[tot].push_back(u);
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == f || vis[v])
            continue;
        vis[v] = 1;
        get_CB(v, u);
    }
}
void get_loop(int u, int f, long long len, int id)
{
    st[++tail] = u;
    if (c[u] != 2)
        c[u] = 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == f)
            continue;
        if (c[v] == 1)
        {
            while (st[tail] != v)
            {
                SCC[id].push_back(st[tail]);
                c[st[tail]] = 2;
                tail--;
            }
            SCC[id].push_back(st[tail]);
            c[st[tail]] = 2;
        }
        if (vis[v])
            continue;
        vis[v] = 1;
        get_loop(v, u, len + e[i].w, id);
    }
    st[tail--] = 0;
    if (c[u] != 2)
        c[u] = 0;
}
map<pair<int, int>, long long> Q;
void GET_DIS_2(int u, int f, int root)
{
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == f || c[v] != 2)
            continue;
        Q[make_pair(min(u, v), max(u, v))] = e[i].w;
        DIS[v] = e[i].w;
        if (v == root)
            return;
        GET_DIS_2(v, u, root);
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int u;
        long long v;
        scanf("%d%lld", &u, &v);
        EDGE.push_back(node{min(i, u), max(i, u), v});
    }
    sort(EDGE.begin(), EDGE.end(), cmp);
    add(EDGE[0].x, EDGE[0].y, EDGE[0].w), add(EDGE[0].y, EDGE[0].x, EDGE[0].w);
    for (int i = 1; i < n; i++)
    {
        if (EDGE[i].x != EDGE[i - 1].x || EDGE[i].y != EDGE[i - 1].y)
            add(EDGE[i].x, EDGE[i].y, EDGE[i].w), add(EDGE[i].y, EDGE[i].x, EDGE[i].w);
    }
    EDGE.clear();
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            tot++;
            get_CB(i, 0);
        }
    }
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= tot; i++)
        get_loop(CB[i][0], 0, 0, i);
    for (int i = 1; i <= tot; i++)
    {
        maxn = 0;
        if (!SCC[i].size())
        {
            maxn = 0;
            dp(CB[i][0], 0);
            ans += maxn;
            CB[i].clear();
            continue;
        }
        GET_DIS_2(SCC[i][0], 0, SCC[i][0]);
        for (auto &P : SCC[i])
            sum[i] += DIS[P], d[P] = dp(P, 0);
        long long max1 = d[SCC[i][0]], max2 = d[SCC[i][0]], max_list = 0, len = 0;
        for (int j = 1; j < SCC[i].size(); j++)
        {
            len += Q[make_pair(min(SCC[i][j - 1], SCC[i][j]), max(SCC[i][j - 1], SCC[i][j]))];
            max_list = max(max_list, d[SCC[i][j]] + max(max1 + len, max2 - len + sum[i]));
            max1 = max(max1, d[SCC[i][j]] - len);
            max2 = max(max2, d[SCC[i][j]] + len);
        }
        ans += max(max_list, maxn);
        CB[i].clear();
        SCC[i].clear();
    }

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