いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…

たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみた！ 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになったか…

部分永続 Union-Find 木の練習をした。 問題概要 N 頂点 M 辺の無向グラフがあります。 グラフは連結です。以下の Q 個のクエリに答えよ: 頂点 x, y が与えられ、「x と y を含む z 個の頂点からなる集合に含まれる頂点の番号の最大値」の最小値を求めよ 解…