以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Committee: 委員会
input ファイル“committee.in”
output 標準出力
ソースファイルcommittee.c/committee.cpp
時間制限1 秒/ データ
情報オリンピック日本委員会は上下関係がとても厳格な組織である.委員長は一人で,委員
長以外の全ての人間はただ一人の上司を持つ.また,機密性を守るため,組織の人間は自分と
直接に関係を持つ人間,つまり自分の直接の上司と直接の部下の顔しか知らない.電子的な手
段や公共の手段を利用してやりとりをすることは許されておらず,顔を知らない者同士がやり
とりをしたい際は,顔を知っている同士である人間をつたってやりとりをしなければいけない.
そして,委員会に属する人間には,一人一人やる気の数値なるものが定まっている.やる気の
数値が負である人間が居ることもある.
今,情報オリンピック日本委員会の中で,ある極秘のプロジェクトを立ち上げることとなり,
一人以上の人間を選ばなければならなくなった.そのプロジェクトが上手くいくかどうかは,選
ばれた人間の人数には関係なく,それらの人間のやる気の数値の合計によると考えられる.た
だし,プロジェクトは極秘なので,プロジェクト内の任意の人間同士がやり取りをする際,プ
ロジェクト外の人間を通さずにやり取りができるようにしなければいけない.
入力としてそれぞれの人間の上司とやる気の数値が与えられた時,条件を満たす選び方の,や
る気の合計の最大値を答えるプログラムを作成せよ.
Input. 入力ファイルcommittee.in の1 行目は1 つの整数n (n ≦100, 000) が書かれている.
これは情報オリンピック日本委員会の人数がn 人であることを表す.
次のn 行には,それぞれの人間の上司とやる気の数値が書かれている.i + 1 行目(1 ≦i ≦n)
には2 つの整数si, ai (0 ≦si < i, −100 ≦ai ≦100) が空白を区切りとして書かれている.これ
は,人間i の上司が人間si であり,人間i のやる気の数値がai であることを表す.si が0 の時,
人間i は委員長であることを表す.si < i であることから,ある人間の上司は必ずその人間の番
号より若い番号を持つ.
Output. 出力は,標準出力に行うこと.やる気の合計の最大値を表す1 つの整数を出力せよ.
委員会–1/2
例
committee.in 標準出力
5 15
0 10
1 5
2 -8
1 -15
4 3
委員会–2/2