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

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

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

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

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

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

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

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

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

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

• 次のパラメータを持つプロシージャ init(N, E):
  • N -- 頂点の数。頂点には 0 から N-1 までの異なる整数の番号がつけられている。
  • E -- 辺の情報を表す整数の 2 次元配列。0 ≦ i ＜ N-1 に対し、辺 i は異なる2つの頂点 E[i][0] と E[i][1] を結んでいる。E は木構造を表していることが保証されている。すなわちどの頂点からどの頂点へも辺をたどって行くことが可能で、かつその経路は 1 通りしか存在しない。
  このプロシージャは最初に query(i) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ query(i):
  • i -- 壊される頂点の番号。
  このプロシージャはちょうど N-1 回呼び出される。1回の呼び出しで1つの頂点が破壊される(この破壊は、それ以前のすべての破壊に続くものである)。すでに破壊された頂点 i がもういちど指定されることはない。ある頂点 i を破壊するとき、その頂点とそれに接続するすべての辺を削除する。それぞれの呼び出しは頂点の破壊の後に残った森(1つ以上の木の集合)について、それぞれの木の頂点数のうち最大のものを返す必要がある。

図1に示される N = 5,

R =	0 1 1 2 2 3 3 4

の場合を考える。

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

図2に示される N = 5,

R =	2 1 0 2 4 0 3 0

の場合を考える。

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