POJ 3321: Apple Tree

問題

N個のノードからなる木構造が与えられており、初期状態では各ノードにリンゴがなっている。この木構造に対して2種類のクエリが合計M個与えられる。1つ目のクエリは、指定されたノードを根とする部分木に何個のリンゴがなっているかを答えるもの、もう1つは指定されたノードのリンゴの状態を反転させるもの(リンゴがあったら無くなり、もしあれば新しく実る)である。このクエリを高速に処理せよ。

制約条件

1 <= N, M <= 100000

解法

与えられる情報から木構造を隣接エッジリストで持ちます。それができたら深さ優先探索で各ノードに行きがけの時に番号を振ります。

これに加えて戻りがけの時の番号も保存しておくと、自分の子ノードの持つ番号の範囲が分かります(子ノードの番号は必ず連続する)。

この性質を利用すると、部分木の持つリンゴの数をBITを使ってO(logN)で計算することができます。

リンゴの状態を反転させるクエリもBITを使えばO(logN)で処理できるので、この方針で十分計算量は足りそうという気がします。

ただ、komiyamさんのブログにも書かれている通り、結構時間の条件が厳しく、木構造を双方向グラフで持つとTLEになります。

大した差ではない気もするのですが、以下に示すコードのように木のエッジを一方向のみ持つ(コメントアウトしてる行がポイント)ようにしたら、ギリギリ1875msくらいでACできました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です