ABC295 G - Minimum Reachable City (600)
解説の解法
各連結成分毎に到達可能な最小値を持っておく
この連結成分は木の下から上に行く方向ののみ
$ uのグループの最小値が$ vより大きい間以下を行う
$ uとその親のそれぞれの最小値の内小さい方を持っておく
$ uとその親をマージ
$ uのグループの最小値を上で持っておいた最小値で更新
$ uをグループ内の最小値で更新
上の操作では1ループ毎に1グループ分の辺を上に昇ることができる
問題: https://atcoder.jp/contests/abc295/tasks/abc295_g
提出: https://atcoder.jp/contests/abc295/submissions/40059483
#ABC295 #600pt #G #ABC #AtCoder
#UnionFind #木 #連結成分