むこのどうぶつたち と しんりんのはかい (Innocent Animals and Destruction of Forests)

きつねの次郎はゆたかな森林でほかのどうぶつたちと楽しく遊んで暮らしていました。

森林のなかにはどうぶつたちの遊び場がたくさんあって、遊び場どうしはいくつかの道で結ばれています。もちろんどの遊び場からどの遊び場にもいくつかの道をたどって行くことができて、ある遊び場からある遊び場へいくための経路は1通りだけあります。

しかしどうぶつたちの幸せな時間は長くは続きませんでした。人間たちがとつぜん森林へやってきて、どうぶつたちの遊び場を壊していくようになったのです。

ある遊び場が人間たちによって壊されてしまうと、そこはもうどうぶつたちには危ないので通ることができません。そうするとどうぶつたちの遊び場が分断されてしまって、ある遊び場からいくことのできない遊び場が現れることになります。

次郎をはじめとするどうぶつたちは何とかしてこれに抵抗したいのですが、彼らの力で人間を止めることは残念ですができません。

しかたがないのでどうぶつたちは、分断されてしまった遊び場たちの中で、これからいちばん長く残りそうなところへ行くことにしました。

どうぶつたちはとてもかわいそうですが、人間による森林の破壊はとどまるようすを見せません。せめて彼らどうぶつたちがすこしでも長く、より多くの遊び場で遊んでいられるように、彼らを助けてほしいのです。

課題

N 頂点からなる木が与えられる。各頂点には 0 から N-1 までの異なる整数の番号がつけられている。

次のプロシージャを実装せよ:

例1

図1
図 1

図1に示される N = 5,
R =
0 1
1 2
2 3
3 4
の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後プロシージャ query が1回の破壊ごとに1回ずつ呼び出される。以下に呼び出しと正しい戻り値の例を示す:

破壊 パラメータ 戻り値
1 query(1) 3
2 query(0) 3
3 query(3) 1
4 query(4) 1

例2

図2
図 2

図2に示される N = 5,
R =
2 1
0 2
4 0
3 0
の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後プロシージャ query が1回の破壊ごとに1回ずつ呼び出される。以下に呼び出しと正しい戻り値の例を示す:

破壊 パラメータ 戻り値
1 query(1) 4
2 query(2) 3
3 query(0) 1
4 query(4) 1

小課題

小課題 1 (20 点)

小課題 2 (25 点)

小課題 3 (55 点)

実装の詳細

制限

インターフェース (API)