题面：[ZJOI2008] 骑士

题目描述

Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。

最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。

骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。

战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。

为了描述战斗力，我们将骑士按照 $1$ 至 $n$ 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

输入格式

第一行包含一个整数 $n$，描述骑士团的人数。

接下来 $n$ 行，每行两个整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

输出格式

应输出一行，包含一个整数，表示你所选出的骑士军团的战斗力。

样例 #1

样例输入 #1

1
2
3
4
3
10 2
20 3
30 1

样例输出 #1

1
30

提示

对于 $30\%$ 的测试数据，满足 $n \le 10$；

对于 $60\%$ 的测试数据，满足 $n \le 100$；

对于 $80\%$ 的测试数据，满足 $n \le 10 ^4$。

对于 $100\%$ 的测试数据，满足 $1\le n \le 10^6$，每名骑士的战斗力都是不大于 $10^6$ 的正整数。

思路

抓取关键字：每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己）

概括一波，n 个骑士 n 个关系，典型的基环树数据结构。然后目光看向这道题目：P1352 没有上司的舞会 - 洛谷 ，是不是十分得有九分的相似？

答对了，这道题从某种意义上来讲就是上司舞会的加强版本。那么继承上司舞会的思路，我们肯定是要把基环树变成树才可以用上司舞会的思路去求解，大致方向就可以确定了。

深入思考一下，我们在基环树的文章中就提到过，基环树大多数有两种方式，这道题就是其二：删除环上一边，使其变成一棵树，然后求解。那么这道题就完全被攻克了qwq

tips: 删除那条边的两个顶点是不可以同时选择的！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

const int MaxV = 1000010;

int n;
ll a[MaxV];
Graph< MaxV, MaxV >G;

int fa[MaxV];

inline void Input() {
    read(n); int v;
    for(int i = 1; i <= n; i++) {
        read(a[i], v);
        G.AddEdge(v, i);
        fa[i] = v;
    }
}

int vis[MaxV], root;
ll ans, dp[MaxV][2];

void Dfs(int u) {
    vis[u] = 1;
    dp[u][0] = 0, dp[u][1] = a[u];
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == root) dp[v][1] = -1e18;
        else {
            Dfs(v);
            dp[u][0] += max(dp[v][1], dp[v][0]);
            dp[u][1] += dp[v][0];
        }
    }
}

inline void GetCircle(int u) {
    root = u;
    vis[root] = 1;
    while(!vis[fa[root]]) {
        root = fa[root]; vis[root] = 1;
    }
    Dfs(root);
    ll t = max(dp[root][0], dp[root][1]);
    vis[root] = 1; root = fa[root];
    Dfs(root);
    ans += max(t, max(dp[root][0], dp[root][1]));
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            GetCircle(i);
            // cout << ans << endl;
        }
    }
    printf("%lld\n", ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}