読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Dynamic connectivity contest: Bridges in a Tree

問題ページ

問題概要

木が与えられる。初期状態に辺 e1, e2 ,..., eK を加えたとき橋はいくつあるかという M 個のクエリを順次処理せよ。

  • 2≦N≦100,000
  • 1≦M≦100,000
  • ΣK≦100,000

解法

いもす法による橋検出アルゴリズムと同様のアプローチを掛ける。具体的には、辺 e=(u,v) を追加すると u-v パス上の辺はすべて橋でなくなることを使う。

これは HL分解+遅延評価セグメント木により高速に行える。

B は辺更新 LC 木を使えば C と同じことができそう。ただ LC 木が amortized なことを考えると D への拡張は難しい。