WA 20pts求调

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

namespace OI {

#define int long long
#define endl "\n"

constexpr int maxn = 1e6+5;
struct edge {
    int to, id;
};
vector<edge> graph[maxn];
int tot;

int n, deg[maxn];


int root, collar, deleted;
void toposort() {
    queue<int> que;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            que.push(i);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto v : graph[u]) {
            deg[v.to]--;
            if (deg[v.to] == 1)
                que.push(v.to);
        }
    }
    
}

bool vis[maxn];
bool collarStat = 0;
int f[maxn][2], score[maxn];
void dfs(int u, int fa) {
    vis[u] = 1;
    f[u][0] = 0;
    f[u][1] = score[u];
    if (u == collar)
        f[u][!collarStat] = -1e18;
    for (auto v : graph[u]) {
        if (v.to == fa || v.id == deleted)
            continue;
        dfs(v.to, u);
        f[u][0] += max(f[v.to][0], f[v.to][1]);
        f[u][1] += f[v.to][0];
        if (u == collar)
            f[u][!collarStat] = -1e18;
    }
}

void main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int hate;
        cin >> score[i] >> hate;
        graph[i].push_back({hate, ++tot});
        graph[hate].push_back({i, tot});
        deg[hate]++, deg[i]++;
    }
    toposort();
    int ret = 0;
    for (int r = 1; r <= n; r++) {
        if (deg[r] == 1 || vis[r])
            continue;
        root = r;
        for (auto v : graph[r]) {
            if (deg[v.to] != 1) {
                collar = v.to;
                deleted = v.id;
                break;
            }
        }
        collarStat = 0;
        dfs(root, 0);
        int ans = max(f[root][0], f[root][1]);
        collarStat = 1;
        dfs(root, 0);
        ans = max(ans, f[root][0]);
        ret += ans;
    }
    cout << ret << endl;
}

#undef int
#undef endl

}

int main() {
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(0);

    OI::main();

    return 0;
}