复杂度是 $O(n)$。
::::info[code]
```cpp
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
#define pb push_back
#define vec vector
#define pii pair<int, int>
#define pll pair<ll, ll>
const int N = 1e5 + 10;
int t;
int n;
int to[N], c[N];
int ind[N], f[N], g[N];
int vis[N];
ll res;
void topo() {
queue< int > q;
for (int i = 1; i <= n; i ++) {
if (!ind[i]) q.push(i), vis[i] = 1;
}
while (!q.empty()) {
int u = q.front(); q.pop();
int v = to[u];
ind[v] --;
g[v] = max(g[v], c[u]);
if (!ind[v]) q.push(v), vis[v] = 1;
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> to[i] >> c[i];
res += c[i];
ind[to[i]] ++;
f[to[i]] = max(f[to[i]], c[i]);
}
for (int i = 1; i <= n; i ++) {
res -= f[i];
}
topo();
int cnt = 0, siz = 0;
for (int i = 1; i <= n; i ++) {
if (vis[i]) continue;
cnt ++;
int mx = -1e9;
int u = i;
do {
siz ++;
vis[u] = 1;
mx = max(mx, g[u] - f[u]);
u = to[u];
} while(u != i);
res -= mx;
}
if (cnt == 1 && siz == n) cout << 0 << '\n';
else cout << res << '\n';
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
clock_t st = clock();
t = 1;
// cin >> t;
while (t --) solve();
clock_t ed = clock();
double _t = double(ed - st) / CLOCKS_PER_SEC;
cerr << "time: " << _t << "s" << '\n';
return 0;
}
```
::::