import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class Main { public static final int FIXED = 10; // O(N ^ 2) public static long calc_DAG(int start, final int N, long[] difficulty, int[] requires, boolean[] visited){ if(visited[start]){ return 0; } LinkedList queue = new LinkedList(); visited[start] = true; queue.add(start); long ret = 0; boolean first = true; while(!queue.isEmpty()){ final int curr = queue.poll(); if(first){ ret += difficulty[curr]; first = false; }else{ ret += difficulty[curr] / 2; } for(int next = 0; next < N; next++){ if(requires[next] != curr){ continue; } if(visited[next]){ continue; } visited[next] = true; queue.add(next); } } return ret; } public static long INF = Long.MAX_VALUE / 2 - 1; public static long find_loop_min(int curr, final int N, long[] difficulty, int[] requires, boolean[] visited){ visited[curr] = true; long ret = INF; //System.out.println(curr + " " + difficulty[curr]); for(int next = 0; next < N; next++){ if(requires[next] != curr){ continue; } if(visited[next]){ ret = Math.min(ret, difficulty[curr]); }else{ final long r = find_loop_min(next, N, difficulty, requires, visited); if(r < INF){ ret = Math.min(ret, Math.min(r, difficulty[curr])); }else{ ret = Math.min(ret, r); } } } visited[curr] = false; //System.out.println(curr + " " + difficulty[curr] + " " + ret); return ret; } public static long calc_loop(int start, final int N, long[] difficulty, int[] requires, boolean[] visited){ if(visited[start]){ return 0; } LinkedList queue = new LinkedList(); visited[start] = true; queue.add(start); long ret = 0; while(!queue.isEmpty()){ final int curr = queue.poll(); ret += difficulty[curr] / 2; for(int next = 0; next < N; next++){ if(requires[next] != curr){ continue; } if(visited[next]){ continue; } visited[next] = true; queue.add(next); } } return ret; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); final int N = sc.nextInt(); long[] difficulty = new long[N]; int[] requires = new int[N]; int[] ins = new int[N]; int[] ous = new int[N]; for(int to = 0; to < N; to++){ difficulty[to] = sc.nextLong() * FIXED; final int from = sc.nextInt() - 1; // if(to == from){ continue; } requires[to] = from; ins[to]++; ous[from]++; } long score = 0; boolean[] visited = new boolean[N]; // 入次数 = 出次数 = 0 (自己ループを消した場合) があったら優先的にクリアする for(int stage = 0; stage < N; stage++){ if(ins[stage] == 0 && ous[stage] == 0 && !visited[stage]){ visited[stage] = true; score += difficulty[stage]; } } // 入次数 = 0 かつ 出次数 >= 1 なら DAG のスタート地点 for(int stage = 0; stage < N; stage++){ if(ins[stage] == 0 && ous[stage] >= 1 && !visited[stage]){ score += calc_DAG(stage, N, difficulty, requires, visited); } } // 以上を処理したあと、ループを処理する // ループのある候補は 入時数 = 出自数 = 1 なのでしらみつぶしに探索 for(int stage = 0; stage < N; stage++){ if(ins[stage] >= 1 && ous[stage] >= 1 && !visited[stage]){ final long min = find_loop_min(stage, N, difficulty, requires, visited); if(min == INF){ continue; } // ループがあったら、そのループから可達なノードをすべて埋める(1/2で) final long loop_score = calc_loop(stage, N, difficulty, requires, visited); //System.out.println(stage + " " + max + " " + loop_score); score += (min / 2) + loop_score; } } for(int stage = 0; stage < N; stage++){ if(!visited[stage]){ score += difficulty[stage]; } } System.out.println((score / FIXED) + "." + (score % FIXED)); } }