競技プログラミング用知識集積所

ABC447E - Divide Graph

最終更新：2026年03月02日 00:10

sport_programming

- view

管理者のみ編集可

問題
必要知識
考え方
解答例
注意点
別解

問題

ABC447E

必要知識

B以下レベルの内容は省略

考え方

i番目の辺のコストが2^iであるということは、ある辺を採用するときに、それより番号が小さい辺を全部採用できなくなったとしても得をするということ。
つまり、コストが高い方から優先的に採用する貪欲法※が成立する。

コストが高い方（番号が大きい方）から順に、可能な限りその辺を残すことに決定する。
辺を残すことにすると、いくつかの頂点は同じ連続成分であることに確定する。
連結成分数がその辺のせいで1にならないようであれば残すことが可能である。
逆に、連結成分数がその辺のせいで1になるのであれば、削除することに決定し、コストを加算する。

連結成分数は頂点情報をUnionFind木※で管理し、非連結だった頂点同士を連結する操作が何回行われたかをカウントしておく。
それがn-2回になるまでは無条件にその辺を残すことができ、n-2回に達した後は元々同じ連結成分に含まれている辺だけ残すことになる。

2^iは、繰り返し二乗法※で逐一高速に計算するか、最初にまとめて計算してメモ化※しておいてもよい。

答えは998244353で割ったものを要求されているので、剰余類環も参照。