← 返回题目列表

AtCoder · joisc2009_distribution

distribution. 小册子分发(Distribution)

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

冊子の配布 (Distribution) - 原题 PDF 第 1 页
原题PDF第1页
冊子の配布 (Distribution) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Distribution: 冊子の配布


input ファイル“distribution.in”
output 標準出力
ソースファイルdistribution.c/distribution.cpp
時間制限2 秒/ データ



 情報オリンピック日本委員会は上下関係がとても厳格な組織である.委員長は一人で,委員

長以外の全ての人間はただ一人の上司を持つ.そして,委員会に属する人間には,一人一人や

る気の数値なるものが定まっている.

 今,情報オリンピック日本委員会の中で,新たなプロジェクトを立ち上げることとなった.そ

のプロジェクトが上手くいくかどうかは,参加する人間の人数には関係なく,参加する人間の

やる気の数値の合計によると考えられている.

 委員長はそのプロジェクトに関する詳細な説明を記述した冊子をm 冊制作した.プロジェク

トに参加する人間は,必ずこの冊子を読まなければならず,冊子を読んだ人間は必ずプロジェ

クトに参加する.

 最初は委員長がm 冊全ての冊子を持っている.委員長及び冊子を1 冊以上渡された人間は,

まず冊子を読み,部下が居れば冊子を部下に渡す.部下とは,その人間を上司として持つ人間

のことである.1 冊の冊子は部下のうちの一人に渡すことができる.同じ部下に2 冊以上の冊子

を渡してもよく,冊子が1 冊も渡されない部下がいても良い.1 度冊子を読めば,手元に冊子を

残しておく必要はない.

 入力としてそれぞれの人間の上司とやる気の数値,そして製作した冊子の冊数m が与えられ

た時,プロジェクトに参加する人間のやる気の合計の最大値を答えるプログラムを作成せよ.

Input.  入力ファイルdistribution.in の1 行目には2 つの整数n, m (1 ≦n ≦10 000,

1 ≦m ≦1000) が空白を区切りとして書かれている.これは情報オリンピック日本委員会の人

数がn 人であり,製作した冊子の冊数がm 冊であることを表す.

 次のn 行には,それぞれの人間の上司とやる気の数値が書かれている.i + 1 行目(1 ≦i ≦n)

には2 つの整数si, ai (0 ≦si < i,1 ≦ai ≦10 000) が空白を区切りとして書かれている.これ

は,人間i の上司が人間si であり,人間i のやる気の数値がai であることを表す.si が0 の時,

人間i は委員長であることを表す.(si < i であることから,ある人間の上司は必ずその人間の

番号より若い番号を持ち,人間1 は必ず委員長である.)


Output. 出力は,標準出力に行うこと.プロジェクトに参加する人間のやる気の合計の最大

値を表す1 つの整数を出力せよ.


                      冊子の配布–1/2

採点基準採点用データのうち,配点の50% 分については,n ≦500, m ≦100 を満たす.


例
 distribution.in 標準出力
 5 2              22
 0 10
 1 3
 2 5
 2 2
 1 4





                      冊子の配布–2/2