Atcoder水色精進記録

アルゴリズム・データ構造

重みつきUnionFind

Xa - Xb = d → Xa = d + Xb
単一の式だけで考えれば、Xaが決まればXbが決まる
関連するa,bに辺が貼られたグラフとして考えれば閉路がなければ条件は成立している
閉路ができる場合、それまでの値と整合性を保てた状態で、繋ぐことができれば条件は成立

UnionFindで閉路検出はできる
UnionFindに重みを追加して、自分のルートとのdiffを保持しておけばOK

重みの更新が手癖で書けないので、書けるまで慣れたい
union時にfindせずにrootを使ってしまう癖があるので直す必要があり