24139번 - 委員会 (Committee) 다국어

문제

情報オリンピック日本委員会は上下関係がとても厳格な組織である.委員長は一人で,委員 長以外の全ての人間はただ一人の上司を持つ.また,機密性を守るため,組織の人間は自分と 直接に関係を持つ人間,つまり自分の直接の上司と直接の部下の顔しか知らない.電子的な手 段や公共の手段を利用してやりとりをすることは許されておらず,顔を知らない者同士がやり とりをしたい際は,顔を知っている同士である人間をつたってやりとりをしなければいけない. そして,委員会に属する人間には,一人一人やる気の数値なるものが定まっている.やる気の 数値が負である人間が居ることもある.

今,情報オリンピック日本委員会の中で,ある極秘のプロジェクトを立ち上げることとなり, 一人以上の人間を選ばなければならなくなった.そのプロジェクトが上手くいくかどうかは,選 ばれた人間の人数には関係なく,それらの人間のやる気の数値の合計によると考えられる.た だし,プロジェクトは極秘なので,プロジェクト内の任意の人間同士がやり取りをする際,プ ロジェクト外の人間を通さずにやり取りができるようにしなければいけない.

入力としてそれぞれの人間の上司とやる気の数値が与えられた時,条件を満たす選び方の,や る気の合計の最大値を答えるプログラムを作成せよ.

입력

入力の 1 行目は 1 つの整数 n (n ≤ 100, 000) が書かれている. これは情報オリンピック日本委員会の人数が n 人であることを表す.

次の n 行には,それぞれの人間の上司とやる気の数値が書かれている.i + 1 行目 (1 ≤ i ≤ n) には 2 つの整数 s_i, a_i (0 ≤ s_i < i, −100 ≤ a_i ≤ 100) が空白を区切りとして書かれている.これ は,人間 i の上司が人間 s_i であり,人間 i のやる気の数値が a_i であることを表す.s_i が 0 の時, 人間 i は委員長であることを表す.s_i < i であることから,ある人間の上司は必ずその人間の番 号より若い番号を持つ.

출력

出力は,標準出力に行うこと.やる気の合計の最大値を表す 1 つの整数を出力せよ.

제한

힌트