#include using namespace std; #define N 100 int n; struct { int level; int pre_stage; int root; } stages[N]; int visit[N]; int search(int no, int term) { if ( visit[no] || stages[no].root ) { // 訪問済み return -1; } if ( stages[no].pre_stage == no ) { // 難易度を下げられるステージは存在しない (自分自身が対象のステージになっている) return no; } if ( no == term ) { // 循環の末端 return no; } visit[no] = 1; // noより前のステージのうち、最小難易度のステージを取得 int min = search(stages[no].pre_stage, term); if ( min < 0 ) { return -1; } // noの難易度と比較し、低い方のステージを返す return stages[no].level < stages[min].level ? no : min; } int main() { cin >> n; for ( int i = 0; i < n; i++ ) { cin >> stages[i].level >> stages[i].pre_stage; stages[i].level *= 10; stages[i].pre_stage--; } // 難易度が下げられるステージと、下げられないステージとに分けられる。 // 難易度が下げられるステージでも、循環している場合はどれか一つは難易度が下げられない。 // その場合は循環するステージのうち、最も難易度が低いものを選択すれば良い。 // 難易度を下げられないステージを探索 // is_root[N].rootに、難易度を下げられないステージには1が設定される。 for ( int i = 0; i < n; i++ ) { if ( !visit[stages[i].pre_stage] ) { // rootに、難易度の下げられないステージが返る int root = search(stages[i].pre_stage, i); if ( root >= 0 ) { stages[root].root = 1; } } } // あとは、.rootが1のステージの難易度はそのまま、0は難易度半分で集計すれば良い。 int level = 0; for ( auto stage : stages ) { level += stage.root ? stage.level : (stage.level / 2); } cout << (level / 10) << "." << (level % 10) << endl; return 0; }