NOI 2019 Finals - Rigged Roads
概要
問題へのリンク
Author : Cyanmond
解法
まず、小課題 2 を考える。
辞書順最小を求めるときは前から貪欲に決めれば良いので、以下のように解ける。
$ i = 1, 2, \cdots ,Eについて順番に以下のことを行う。
$ W_iがすでに決まっている場合何もしない。
辺$ iが$ Rに含まれている場合、$ W_iにまだ使われていない最小の値を割り当てる。
以上のいずれでもない場合、全域木$ Rの$ A_i - B_iパス上の辺のうちまだ値が割り当てられてないものに、適切な順番にまだ使われていない最小の値を割り当てる。その後$ W_iにまだ使われていない最小の値を割り当てる。
これの計算量は$ O(NE)となる。
HLD を用いて高速化することを考える。ある辺に値が割り当てられるのは$ 1回のみなので、 std::set などと組み合わせることで計算量が$ O(N \log^2 N +E \log N)となる。実装例 管理をもう少し上手にやると$ O(E \log N)にまで計算量が落ちる。また、計算量オーダーの改善ではないが std::set の代わりに Segment Tree を使うなどの高速化も有効と思われる。