Official

M - 筆塗り Editorial by camypaper


様々な解法がありますが、その一例を紹介します。 頂点 \(1\) を根とした根付き木として考えると、頂点 \(u_i,v_i\) 間の最短経路上の辺を色 \(c_i\) で塗る、という操作は \(\mathrm{LCA}(u,v)\) を頂点 \(u,v\) の最小共通祖先として以下の \(2\) つの操作に置き換えられます。

  • 頂点 \(u_i,\mathrm{LCA}(u_i,v_i)\) 間の最短経路上の辺を色 \(c_i\) で塗る
  • 頂点 \(v_i,\mathrm{LCA}(u_i,v_i)\) 間の最短経路上の辺を色 \(c_i\) で塗る

このように操作を \(2\) つの操作に置き換えると、頂点から先祖をたどるという操作だけを考えればよく問題が単純になります。

各辺について、最後に色を塗られるタイミングがわかれば問題の答えを求めることができます。 そこで、操作を逆順から見て以下のように問題を言い換えます。

\(N\) 頂点の木が与えられ、\(Q\) 回操作が行われる。はじめ、どの辺も色が塗られていない。 \(i\) 回目の操作では、頂点 \(u_i,v_i\) 間の最短経路上の辺のうち、まだ色が塗られていない辺を色 \(c_i\) で塗る。 最終状態におけるそれぞれの辺の色を求めよ。

頂点たちを素集合データ構造で管理することにして、ある辺に色が塗られたタイミングでその辺の両端のグループをマージすることにします。 各グループについて最も根に近い頂点を覚えておくことにすると、\(i\) 回目の操作では端点から最小共通先祖までの経路上にまだ塗られていない辺が存在する限りマージを繰り返せばよいです。

最小共通先祖を調べるための前処理に \(O(N \log N)\)、最小共通先祖の取得を \(O(\log N)\) として全体として \(O((N+Q) \log N)\) で実行可能で十分高速です。

posted:
last update: