ひらめの日常

プログラミングと読書と

union_find

Codeforces Round #582 (Div. 3) G. Path Queries

問題はこちら codeforces.com 頂点数 の木が与えられる(木なので辺の数は )。 以下のような 個のクエリ が投げられるので、それぞれに対する答えを出力せよ。 求めるものは以下を満たす頂点 , , のペアの個数。 頂点 と を結ぶパスの中で、辺の最大の重み…

ABC040-D 道路の老朽化対策について (500)

道路の老朽化対策について タイトルだけ見ると政策の説明みたいだけど、競技プログラミングの問題。 問題はこちら。 atcoder.jp 都市をつなぐ道路が与えられるので、都市を頂点、道路を辺としてみたグラフを考えることにする。 Unionfindを使ってクエリごと…