#ijpcanimals. [ijpc_animals]むこのどうぶつたち と しんりんのはかい (Innocent Animals and Destruction of Forests)
[ijpc_animals]むこのどうぶつたち と しんりんのはかい (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
図 1
図1に示される N = 5,
E =
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に示される N = 5,
E =
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 点)
- 1 ≦ N ≦ 1 000
小課題 2 (25 点)
- (この小課題に限っては)木は直線状になっている。
すなわちすべての i について E[i][0] = i, E[i][1] = i+1 が成り立つ。 - 1 ≦ N ≦ 100 000
小課題 3 (55 点)
- 1 ≦ N ≦ 100 000
実装の詳細
制限
- CPU 時間制限: 2秒
- メモリ制限: 64 MB
注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。
インターフェース (API)
- 実装フォルダ: animals/ (プロトタイプ: animals.zip)
- 競技者が実装するファイル: animals.cpp
- 提出ファイルのインターフェース: animals.h
- 採点プログラムのサンプル: grader.cpp
- 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
**注意:**採点プログラムのサンプルは次の書式の入力を読み込む。- 1 行目: N
- 2 行目から N 行目: 0 ≦ i ＜ N-1 に対し、i+2 行目には E[i][0] と E[i][1] が空白区切りで書かれている。
- N+1 行目: N-1 個の整数 I[0], I[1], ..., I[N-2] が空白区切りで書かれている。I[i] は i 個目に破壊される頂点の番号である。
- 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
**注意:**採点プログラムのサンプルは次の書式の出力を書き出す。- 1行目: N-1 個の整数 X[0], X[1], ..., X[N-2] が空白区切りで出力される。X[i] は i 回目の query 呼び出しの際に返されるべき戻り値である。