はまやんはまやんはまやん

hamayanhamayan's blog

帰省ラッシュ [yukicoder No.529]

http://yukicoder.me/problems/no/529

前提知識

hamayanhamayan.hatenablog.jp
hamayanhamayan.hatenablog.jp

  • UnionFind
  • セグメントツリー

解法

https://yukicoder.me/submissions/179292

事前処理
1. 無向グラフを二重辺連結成分分解する
2. 各成分を1つの頂点に縮約する(これで無向グラフが木になる)
3. できた木でHL分解をする
4. 頂点にある獲物の最大値を保持するセグメントツリーを用意する
クエリ処理1
1. 対応する頂点のpriority_queueに追加する
2. 最大値を更新するようなら、セグメントツリーの対応する要素を更新する
クエリ処理2
1. HL分解されたものを利用して木上のパスで最大の要素を探す
2. 最大の要素があれば、それをセグメントツリーと対応するpriority_queueから削除する
3. 削除したあとにpriority_queueにまだ要素が残っているなら、セグメントツリーに残りの最大値を入れて更新する