問題ページ
問題概要
木が与えられる。初期状態に辺 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 への拡張は難しい。
