ABC203 C Friends and Travel costs
まず, あらかじめ友達を$ A_iの昇順にソートしておく. すると友達を前から順に見ていくと, 前の友達がどこにいるかという情報を持っておくことで, 太郎君の最終的にたどり着く村の番号は高速に求められる. 計算量はソートがボトルネックとなり$ O(N \log N)となる.
実装例: https://atcoder.jp/contests/abc203/submissions/23042003