Highway(高速道路) - joi2010-day4 解説

筆者: qnighy

重み(有向重み)つき無向木が与えられるとき、その重みの更新と、2点間の経路の距離の検索クエリを両方高速で処理させる問題である。

O(NM)解法

木を普通のグラフとして保持しておき、DFSなどを適用すれば、O(NM)となる。

このとき、20点が期待できる。

…

このような場合に使えるのが、DFSを用いて付けた順序である。

辺を進むときと辺を戻る時、どちらの場合でも通過した頂点を記録する。すると例えば次のような木のとき:

対応する数列は、「0, 1, 2, 1, 3, 1, 4, 1, 0, 5, 6, 5, 0, 7, 8, 7, 9, 7, 0」となる。

(このとき、頂点の番号もDFSの初回訪問順に付け直しておく。)

このとき、木の各頂点はこの数列における区間と対応し、木の頂点の子孫関係は数列の区間の包含関係と対応する。

このとき、まず、最近共通祖先(Last Common Ancestor, LCA)を求めるオンラインアルゴリズムを与えよう。

この数列において、2つの頂点に対応する区間を考える。その2つの区間を両方包含する最小の区間を考え、その中での最小の値を探す。(最小の値は予めRMQ,Range Minumum Queryで計算できるようにしておく)その値がLCAである。

例1: 「0, 1, ², 1, 3, 1, ⁴, 1, 0, 5, 6, 5, 0, 7, 8, 7, 9, 7, 0」のとき、²と⁴の間にある値のなかで一番小さいのは1

例2: 「0, [1, 2, 1, 3, 1, 4, 1], 0, 5, 6, 5, 0, 7, 8, 7, ⁹, 7, 0」のとき、[1,2,1,3,1,4,1]と⁹の間にある値のなかで一番小さいのは0

また、ある頂点からその子孫までの距離も、この区間を用いて高速に計算できる。

この数列は辺の行きと帰りに相当するので、その辺にかかるコストとその符号を反転した値を数列に記憶しておく。

例えば初期値は、「0 (1) 1 (1) 2 (-1) 1 (1) 3 (-1) 1 (1) 4 (-1) 1 (-1) 0 (1) 5 (1) 6 (-1) 5 (-1) 0 (1) 7 (1) 8 (-1) 7 (1) 9 (-1) 7 (-1) 0」となる。

辺(1→4)を8で、(0→7)を5で上書きすると、「0 (1) 1 (1) 2 (-1) 1 (1) 3 (-1) 1 (8) 4 (-8) 1 (-1) 0 (1) 5 (1) 6 (-1) 5 (-1) 0 (5) 7 (1) 8 (-1) 7 (1) 9 (-1) 7 (-5) 0」となる。

このとき、0からその子孫4までの距離は、「0 (1) 1 (1) 2 (-1) 1 (1) 3 (-1) 1 (8) 」内の括弧を足しあわせて、9だとわかる。

このときの総和はBIT(Binary Indexed Tree)などで予め計算できるようにしておく。

このことによって一回のクエリをlogNで処理できるので、前処理を含めると((N+M)logN)で処理できる。

この方法で満点が期待できる。