#include #include #include #include #include #include #include using namespace std; int main() { int n; cin >> n; vector level(n+1, 0), prev(n+1, 0); vector< vector > next(n+1, vector()); for (int i = 1; i <= n; i++) { cin >> level[i] >> prev[i]; level[i] *= 10; next[prev[i]].push_back(i); } // 非循環部分の計算と除去 int ans = 0; bool update = true; vector used(n+1, false); used[0] = true; vector::iterator it; int count = 0; while(update) { update = false; for (int i = 1; i <= n; i++) { if (!next[i].empty() || used[i]) { continue; } used[i] = true; ans += level[i] / 2; update = true; for (int j = 1; j <= n; j++) { if (!next[j].empty()) { next[j].erase(remove(next[j].begin(), next[j].end(), i), next[j].end()); } } } } // 循環ごとにまとめる vector< set > group; for (int i = 0; i <= n; i++) { if (used[i]) { continue; } set cycle; queue que; for (que.push(i); !que.empty(); que.pop()) { int num = que.front(); cycle.insert(num); used[num] = true; for (int i = 0; i < next[num].size(); i++) { int tmp = next[num][i]; if (!used[tmp]) { que.push(tmp); } } } group.push_back(cycle); } // 循環部分毎に最小になるように計算 for (int i = 0; i < group.size(); i++) { int sum = 0; int pos = 0; int minlevel = 1e8; for (auto its = group[i].begin(); its != group[i].end(); its++) { sum += level[*its]; if (minlevel > level[*its]) { minlevel = level[*its]; pos = *its; } } ans += (sum - level[pos]) / 2 + level[pos]; } printf("%.1f\n", 0.1 * ans); return 0; }