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
| #include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 100010;
int n, to[N], c[N], In[N], tmp[N], val[N]; ll ans, f[2][2][N];
vector<int> e[N], a, cir, hv[N];
bool vis[N], used[N];
queue<int> q;
bool check() {
int u = 1; rep(i, 1, n) { if(vis[u]) return 0; vis[u] = 1, u = to[u]; }
if(u == 1) return 1; return 0;
}
void Find(int x) {
vis[x] = 1, a.pb(x); if(!vis[to[x]]) Find(to[x]);
for(auto v : e[x]) if(!vis[v]) Find(v);
}
void solve(int x) {
a.clear(), cir.clear(), Find(x); int lst = a[0];
for(auto v : a) tmp[v] = In[v];
for(; !q.empty(); q.pop()); for(auto v : a) if(!In[v]) q.push(v);
if(q.empty()) {
int mn = 2e9; for(auto v : a) mn = min(mn, c[v]); ans += mn; return ;
}
for(int u; !q.empty();) {
u = q.front(), q.pop(), used[u] = 1;
if(hv[u].size() > 1) {
sort(hv[u].begin(), hv[u].end());
rep(i, 0, (int)hv[u].size() - 2) ans += hv[u][i];
}
if(In[to[u]] > 1) hv[to[u]].pb(c[u]);
lst = to[u], --tmp[to[u]]; if(!tmp[to[u]]) q.push(to[u]);
}
cir.pb(lst); for(int u = to[lst]; u != lst; u = to[u]) cir.pb(u);
for(auto v : cir) {
sort(hv[v].begin(), hv[v].end());
rep(i, 0, (int)(hv[v].size() - 2)) ans += hv[v][i];
if(hv[v].size()) val[v] = hv[v].back();
}
f[0][0][0] = c[cir.back()], f[1][1][0] = val[cir[0]];
f[1][0][0] = f[0][1][0] = (ll)1e14;
rep(i, 1, (int)(cir.size() - 1)) {
f[0][0][i] = min(f[1][1][i - 1], min(f[0][1][i - 1], f[0][0][i - 1])) + c[cir[i - 1]];
f[0][1][i] = min(f[0][1][i - 1], f[0][0][i - 1]) + val[cir[i]];
f[1][0][i] = (ll)1e14;
f[1][1][i] = f[1][1][i - 1] + val[cir[i]];
}
ans += min(f[0][0][(int)(cir.size() - 1)], f[0][1][(int)(cir.size() - 1)]);
}
int main() {
scanf("%d", &n);
rep(i, 1, n) scanf("%d%d", &to[i], &c[i]), e[to[i]].pb(i), ++In[to[i]];
if(check()) { puts("0"); return 0; }
memset(vis, 0, sizeof(vis));
rep(i, 1, n) if(!vis[i]) solve(i);
printf("%lld\n", ans);
return 0;
}
|