//#include #include //#include using namespace std; //using namespace atcoder; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair p; const int INF = 1e9; const ll LINF = ll(1e18); const int MOD = 1000000007; const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; #define yes cout << "Yes" << endl #define YES cout << "YES" << endl #define no cout << "No" << endl #define NO cout << "NO" << endl #define rep(i, n) for (int i = 0; i < n; i++) #define ALL(v) v.begin(), v.end() #define debug(v) \ cout << #v << ":"; \ for (auto x : v) \ { \ cout << x << ' '; \ } \ cout << endl; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } //cout<> g; vector> to, from; vector comp, order, used; StronglyConnectedComponents(vector> &g) : g(g), to(g.size()), from(g.size()), comp(g.size(), -1), used(g.size()) { for (int i = 0; i < g.size(); i++) { for (auto x : g[i]) { to[i].push_back(x); from[x].push_back(i); } } } int operator[](int k) { return comp[k]; } void dfs(int now) { if (used[now]) return; used[now] = true; for (int x : to[now]) dfs(x); order.push_back(now); } void rdfs(int now, int cnt) { if (comp[now] != -1) return; comp[now] = cnt; for (int x : from[now]) rdfs(x, cnt); } vector> build() { vector> t; for (int i = 0; i < to.size(); i++) dfs(i); reverse(order.begin(), order.end()); int ptr = 0; for (int i : order) if (comp[i] == -1) rdfs(i, ptr), ptr++; t.resize(ptr); for (int i = 0; i < g.size(); i++) { for (auto v : to[i]) { int x = comp[i], y = comp[v]; if (x == y) continue; t[x].push_back(y); } } return t; } }; vector l; void dfs(int k, vector> &t, vector> &u, vector &used, double &ans) { used[k] = true; rep(i,u[k].size()){ ans += l[u[k][i]]/2; } rep(i,t[k].size()){ dfs(t[k][i],t,u,used,ans); } return; } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector> g(n); vector s(n); l.resize(n); rep(i, n) { cin >> l[i] >> s[i]; s[i]--; g[s[i]].push_back(i); } StronglyConnectedComponents scc(g); vector> t = scc.build(); //debug(scc.comp); vector> u(t.size()); //u[i]:iに含まれる成分 rep(i, n) { u[scc[i]].push_back(i); } vector used(t.size(), false); double ans = 0; rep(i, t.size()) { if (!used[i]) { double temp = 100000000; rep(j, u[i].size()) { chmin(temp, l[u[i][j]]); } ans += temp / 2; dfs(i, t, u, used, ans); } } cout << fixed << setprecision(1); cout<