思路是并查集查询森林里每棵基环树多出来的那条边存起来. 对于每一条这样的边都做3次dfs, 对应了多余的这条边的两个端点同时不选或只选一个的三种情况, 取最大.(其实就是拿城市环路的代码改的

评论区给的hack数据都试过没有问题, 1恨2,2恨1的重边也试过了貌似没问题, 求改正或hack, 万分感谢!

代码如下:

#include <bits/stdc++.h>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define endl '\n'

using namespace std;

__attribute__((unused)) typedef long long ll;
__attribute__((unused)) typedef unsigned long long ull;

__attribute__((unused)) inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

__attribute__((unused)) const long double Pi = 3.1415926535897932384626433832795;
__attribute__((unused)) const int maxN = 1e6 + 4, maxM = 1e5 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;
int p[maxN] = {};
int father[maxN] = {}, Rank[maxN] = {};

void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        Rank[i] = 1;
    }
}

int find(int x) {
    return x == father[x] ? x : find(father[x]);
}

void merge(int i, int j) {
    int x = find(i), y = find(j);
    if (Rank[x] <= Rank[y]) {
        father[x] = y;
    } else
        father[y] = x;
    if (Rank[x] == Rank[y] && x != y) {
        ++Rank[y];
    }
}

/**
for (int i = head[u]; ~i; i = nxt[i]) {
    int v = to[i];
}
 */

vector<int> nxt, head, to;

void add(int u, int v) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

ll dp[2][maxN] = {};
bool checked[2][maxN] = {};

ll dfs(bool isChosen, int u, int fa, int ign) {
    if (checked[isChosen][u])
        return dp[isChosen][u];

    ll tmp = p[ign];
    if (fa == -1) {
        p[ign] = -INF;
    }
    checked[isChosen][u] = true;
    ll ans = isChosen ? p[u] : 0;
    for (int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if (v == fa)
            continue;
        if (isChosen) {
            ans += dfs(false, v, u, ign);
        } else {
            ans += max(dfs(true, v, u, ign), dfs(false, v, u, ign));
        }
    }

    if (fa == -1) {
        p[ign] = tmp;
    }
    return dp[isChosen][u] = ans;
}

vector<int> x, y;

int main() {
    n = read();
    head.resize(n + 1, -1);
    init();
    int v;
    for (int i = 1; i <= n; ++i) {
        p[i] = read(), v = read();
        if (find(i) == find(v)) {
            x.push_back(i);
            y.push_back(v);
            continue;
        }
        merge(i, v);
        add(i, v);
        add(v, i);
    }
    if (n == 1) {
        cout << p[1];
        return 0;
    }

    ll ans = 0;
    for (int i = 0; i < x.size(); ++i) {
        ll tmp = max(dfs(true, x[i], -1, y[i]), dfs(false, x[i], -1, y[i]));
        memset(dp, 0, sizeof dp);
        memset(checked, 0, sizeof checked);
        tmp = max(tmp, dfs(true, y[i], -1, x[i]));
        ans += tmp;
    }

    cout << ans;

    return 0;
}