- Quiz
- Weighted Union Find Trees
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp
- Submit
- 学習
- けんちょんさんの記事で学んだ
- https://qiita.com/drken/items/cce6fc5c579051e64fab
ライブラリ
struct WeightedUnionFind{ VI par; VI rank; VI diff_weight; WeightedUnionFind(ll sz){ init(sz); } void init(ll sz){ par.resize(sz); rank.resize(sz); diff_weight.resize(sz); FOR(i, 0, sz){ par[i] = i; rank[i] = 0; diff_weight[i] = 0; } } int root(ll x) { if (par[x] == x) { return x; } else { ll r = root(par[x]); diff_weight[x] += diff_weight[par[x]]; return par[x] = r; } } ll weight(ll x) { root(x); return diff_weight[x]; } bool is_same(ll x, ll y) { return root(x) == root(y); } // weight(y) - weight(x) = w となるように merge する bool merge(ll x, ll y, ll w) { w += weight(x); w -= weight(y); x = root(x); y = root(y); if (x == y) return false; if (rank[x] < rank[y]) swap(x, y), w = -w; if (rank[x] == rank[y]) ++rank[x]; par[y] = x; diff_weight[y] = w; return true; } ll diff(int x, int y) { return weight(y) - weight(x); } };
その他
- rankは「必要?」と思いつつもそのまま入れた
- 木を結合するときに深くなりすぎない効果
- Weighted UFは「差分制約」言い換えると「相対情報」を扱える
他の問題
Problem F: Never Wait for Weights
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330
- 2つの重みの差の情報と、「AとBの重さの差」のクエリが与えられるので応える
- AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4077829
D - People on a Line
- https://atcoder.jp/contests/abc087/tasks/arc090_b
- (WUF解) AC✅ https://atcoder.jp/contests/abc087/submissions/9150197
- Weighted UFを使わなくても解ける
Consistet Unit System