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
#木
#連結成分