CODE FESTIVAL 2015 Final I 風船ツリー

注意

~~この記事を書いた人はまだACしていません~~

解けました (2015/11/16)

問題

http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_i

前提

整数のmultiset (日本語では多重集合と呼ぶそうです by @climpet さん) Sに対して，多重集合への要素の追加Add，多重集合からの要素の削除Remove，ある整数xよりも大きい値を持つ要素の数を計算する操作CountMoreThanが実現できるデータ構造があるとする。競プロではBITを使う方法がよく使われる。多重集合の要素となり得る値の範囲が大きいなら，座標圧縮する。

解法

(問題の風船ツリーでは根が下にあって葉が上にあるので，以下の説明では「高い」「低い」の使い方がまぎらわしいです)

ある辺e以下の部分木の中で最も高い頂点の高さがmax_height(e)という関数で得られるとする (値は前計算しておく)。

例として，以下の図においてv2が最も高い頂点となるようにするために切断しなければならない辺を数えることを考える。

f:id:kujira16:20151115002141p:plain

辺の集合E(v)を以下のように定義する

E(v) := {根から頂点vまでのパス上の頂点に接続している辺の集合} - {根から頂点vまでのパスに含まれる辺の集合}

この図の場合，E(v2)={e2, e3, e4, e6}となる (↑E(v)の定義が怪しいですが，図から雰囲気で察してください)。

また，max_height(e)の多重集合S(v)を以下のように定義する。

S(v) := {max_height(e) | e ∈ E(v)}

ここで，S(v2)に対してCountMoreThan(height(v2))を計算すれば，最も高い頂点の高さがheight(v2)となるために切断しなければならない辺の数が分かる。今の例だと S(v2)={3, 4, 4, 2} であり，height(v2)=2より大きい要素は3つあって，{e2, e3, e4}を削除すれば風船ツリーの高さが2になる。

重要なのは，全ての頂点vに対してE(v)とS(v)を求めようと思ったときに，オイラーツアーで訪れる順にvを変えていけばE(v)とS(v)の更新が容易に行えることである。これは，以下のような操作を行う。