思路与算法

每个节点连向其最讨厌的人，形成若干基环树。先按入度0剥叶，累积不选该节点zero及选该节点one两种收益：父不选可取孩子两态最大，父选只能取孩子不选。剩余每个有向环按顺序做线性独立集DP，分别强制首点选/不选，首点选时末点必须不选，取优后汇总所有分量。

正确性说明

函数图每个分量恰有一个环，剥叶顺序保证树孩子都先聚合。独立集的选/不选转移完整表达相邻不能同时选。环的唯一额外约束是首尾不能同时选，用两次首点状态覆盖全部合法环方案。分量之间无约束，最优收益相加。互相讨厌的二环虽对应重复无向约束，环DP仍只禁止同时选，不重复计算权值。

复杂度

时间O(N)、空间O(N)，初始化入度和两收益数组O(N)包含在内。N≤10^6，权重≤10^6，总收益≤10^12，用long long；迭代剥叶和环DP不使用百万层递归。

易错点

不能只把图当普通树，也不能忽略二环。剥叶只在入度归0时入队，剩余正入度才是环点。独立答案对小N枚举全部子集；满规模二环对、长链和偶环分别用成对最大值、路径DP及均匀环公式验证。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> to(n), deg(n);
    vector<long long> zero(n), one(n);
    for (int i = 0; i < n; ++i) {
        cin >> one[i] >> to[i];
        --to[i];
        ++deg[to[i]];
    }
    vector<int> q;
    q.reserve(n);
    for (int i = 0; i < n; ++i)
        if (!deg[i])
            q.push_back(i);
    for (size_t at = 0; at < q.size(); ++at) {
        int u = q[at], v = to[u];
        zero[v] += max(zero[u], one[u]);
        one[v] += zero[u];
        if (--deg[v] == 0)
            q.push_back(v);
    }
    long long answer = 0, NEG = -(1LL << 60);
    for (int start = 0; start < n; ++start)
        if (deg[start]) {
            vector<int> cycle;
            int u = start;
            do {
                cycle.push_back(u);
                deg[u] = 0;
                u = to[u];
            } while (u != start);
            long long best = 0;
            for (int first = 0; first < 2; ++first) {
                long long a = first ? NEG : zero[start], b = first ? one[start] : NEG;
                for (size_t i = 1; i < cycle.size(); ++i) {
                    int v = cycle[i];
                    long long na = max(a, b) + zero[v], nb = a + one[v];
                    a = na;
                    b = nb;
                }
                best = max(best, first ? a : max(a, b));
            }
            answer += best;
        }
    cout << answer << '\n';
}