関係式付き Union Find


ポテンシャル付き Union Find [^pot] と呼ばれるものの一般化について、いろんなパターンを網羅しようとすると混乱したので、考えた結果をメモします。

[^pot]: 厳密な定義は見たことないですが、例 1 のようなイメージです


# 前提

[^domain]: $R$ は $1$ を持つ可換環であり、かつ $\forall a,\ b \in R$ について $ab=0$ ならば $a=0$ または $b=0$ 
[^subgroup]: $S = R^{×}$ と思っても良いですが、差のみの整数環の場合などは真部分群になります。

$R$ を可換整域 [^domain] 、その商体を $\mathrm{Frac}(R)$ とします。以下、四則演算・逆元・単元（ $1$ ）などはすべて $\mathrm{Frac}(R)$ 上で考えるものとします。

$S \subset R$ を乗法群 $R^{×}$ の部分群とします [^subgroup]。すなわち次の条件を満たすとします。
- $1 \in S$
- $\forall a \in S$ について $a^{-1} \in S$
- $\forall a,\ \forall b \in S$ について $ab \in S$

さらに $\overline{R} \subset \mathrm{Frac}(R)$ を
- $\overline{R} = R \cup \\{(1-a)^{-1}\cdot x\ |\ a \in S,\ a \neq 1,\ x \in R \\}$

で定義します。
$\overline R$ は和については閉じていますが、積については閉じていないことに注意してください。ただし $R$ の元をかける操作については閉じています。
$\overline R$ は後述のクエリの結果出てくる可能性がある値と（集合として）一致します。理論上は$\overline R$ の代わりに $\mathrm{Frac}(R)$ で考えるとらくかもしれませんが、実装上 $\mathrm{Frac}(R)$ まで拡張しなくて良い場合もあるのでこの定義にしています [^ovreliner]。

[^ovreliner]: 後述の「整数環（和・差）」などの例でありがたみがあるかもしれません。

# クエリ

$i=1,\ \cdots,\ N$ について $v_i \in R$ が対応しているとします。最初 $v_i$ についての情報はありません。
次の $3$ 種類のクエリを処理したいです。以下クエリにおいて $1\le i,\ j\le N$ 、 $a\in S$ 、 $b \in R$ とします。

$1$ $i$ $j$ $a$ $b$
$v_j=a\cdot v_i+b$ という関係式を追加する [^ij]
[^ij]: $i=j$ も許容します

$2$ $i$
$v_i$ の値の可能性がいくつ存在するか [^howmany] 、およびひとつの場合はその値を答える

$3$ $i\ j$
$v_i$ および $v_j$ の値が定まっていないとき、その関係式を答える。すなわち $v_j=a\cdot v_i + b$ をみたす $a \in S,\ b \in R$ （関係式がまだない場合はその旨）を答える [^ifrel] 。

[^ifrel]: 値が定まっているときにどう答えるかは問題によっていろんなパターンがあるが本質ではないのでここではあまり厳密に考えない



[^howmany]: 関係式がまだない（複数の可能性がある）、ちょうどひとつに定まる、既に矛盾が発生していて可能性がない、の 3 パターンあります
[^normalUF]: クエリ $1$ において、 $i$ と $j$ を結ぶという操作だけをするクエリ

# 性質・考察

前節のクエリを「関係式付き Union Find クエリ」と呼びます。
このクエリと通常の Union Find クエリ [^normalUF] と比べてみましょう。
 $a$ が可逆であることから、通常の UF の意味で連結な $2$ 点の間には関係式が定まることが分かります。
実はこの逆は成立しません。これは関係式付き Union Find クエリでは、（通常の UF の意味で）「連結」ではない $2$ 点についても、両方の値が分かっている場合があるからです [^relorig] 。

[^relorig]: どちらも値が分かっている $2$ 点については関係式が（場合によってはたくさん）作れます。それはそれとして、問題によっては通常の Union Find クエリの意味での連結成分が重要になることもあります

連結成分というと、関係式が分かっているという意味と、通常の UF クエリの意味で連結であるという意味のふたつがあることになります。通常の UF クエリの意味での連結成分を「グループ」と呼ぶことにします。ある頂点の値が確定すれば、同じグループ内のすべての頂点の値が確定します。値が確定しているグループを Type A 、そうでないグループを Type B と呼びます。クエリ 1 における新たな情報は、次の $5$ パターンがあります。

1. 追加情報がない
1. 矛盾を発生する
1. Type B のグループにループを発生することによって、そのグループの値をすべて確定する
1. Type A のグループと Type B のグループを結ぶ関係式によって、 Type B 側の頂点の値をすべて確定する
1. $2$ つの異なる Type B のグループについて関係式を与えることによって、ひとつの Type B のグループにする

ここで、ひとつの Type B のグループ内の $2$ 点間についてのクエリでは、 1. 2. 3. のいずれかになることがポイントです。つまり、連結グループ内に追加情報が少しでもあればグループ内のすべての頂点の値を確定できます。なおここで $R$ が整域であることを使っています [^nondomain]。

[^nondomain]: 整域でなければ、例えば $\mathbb{Z}/6\mathbb{Z}$ で $v_i=3v_i+4$ という関係式ができたとすると、「 $v_i=1$ またｈ $v_i=4$ 」という追加情報が得られるが $v_i$ は定まらない、というようなことが起こりえます。

具体的には、 $v_j=a_1 \cdot v_i + b_1$ という関係式がある $2$ 点について、新たに $v_j = a_2 \cdot v_i + b_2$ という情報を追加したとしましょう。 $v_j$ を消去すると $(a_1-a_2)v_i=b_2-b_1$ となります。ここで $a_1=a_2$ かつ $b_1=b_2$ であれば追加情報はありません。そうでなく $a_1=a_2$ であれば矛盾が発生します。そうでなければ $v_i=(b_2-b_1) \cdot (a_1-a_2)^{-1}$ となり $v_i$ が（したがって $v_j$ も）確定します。さらに $a_1-a_2 =a_1(1-a_2\cdot a_1^{-1}) \in S$ かつ $b_2-b_1 \in R$ なので $v_i \in \overline{R}$ も分かります。


# 実装の方針

通常の Union Find の実装に加えて、各グループでの代表元との関係を持っておきます。すなわち $i$ が属するグループの代表元を $r_i$ とすると $v_i = a\cdot v_{r_i} + b$ となる $(a,\ b)$ の組を持っておけばよいです。さらに値が定まっている場合はその値も持っておきます。値が確定する場合は、グループ内のすべての頂点における値を明示的に求めても良いですが、代表元の値だけ持っておいて必要に応じて計算する方法でも実現できます。
    
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">一個値がわかれば代表元の値もわかるので、単に代表元の値がわかってるかどうかと、わかってるならいくつかさえ持っておけば判明したときに全部に適用する必要とかはなさそうです</p>&mdash; のいみ (@noimi_kyopro) <a href="https://twitter.com/noimi_kyopro/status/1599117638508371970?ref_src=twsrc%5Etfw">December 3, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


# 例

## 実数体

$R=\overline{R}=\mathbb{R},\ S=\mathbb{R}-\\{0\\}$ です。
理論的にはきれいですが、 Float 誤差の問題もあり、正確に実現するのは難しそうです。

## mod P

$R=\overline{R}=\mathbb{Z}/p\mathbb{Z},\ S=(\mathbb{Z}/p\mathbb{Z})^{×}$ です。こちらは理論も実装も扱いやすいですね。 $P$ が前計算できないぐらい大きいときは逆元の計算に $\log$ が付きます。


## Z/2Z

上に含まれますが $P=2$ の場合です。この場合はクエリ $1$ をいくらやっても値が確定することはありません。

## 整数環（差のみ）


$R=\overline{R}=\mathbb{Z},\ S=\\{1\\}$ です。関係式では $2$ 数の差が与えられます（つまり $v_j=v_i+b$ の形で表されます） [^potential] 。

[^potential]: 通常、ポテンシャル UF と言うとこれを指すことが多いと思います。


## 整数環（和・差）

$R=\mathbb{Z},\ S=\\{1,-1\\},\ \overline{R}=\\{\displaystyle\frac{x}{2}\ |\ x\in \mathbb{Z}\\} \subsetneqq \mathrm{Frac}\mathbb{(Z)}$ です。先ほどの例の拡張で、 $2$ 数の和または差が与えられます。ここで初めて $\overline{R}$ を定義した効果がでてきています。 $S$ は可逆元のみを動くので、 $v_i$ として出てくる可能性があるのは半整数 [^half_integer] のみです。実装上は、有理数クラスのようなものは不要で、 $2$ 倍の値を整数として保持するので十分です。見た目が気持ち悪いのがやや気になりますが。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">one = 2 、見た目がそこそこ気持ち悪い <a href="https://t.co/SZvzF7tyNK">pic.twitter.com/SZvzF7tyNK</a></p>&mdash; きり (@kiri8128) <a href="https://twitter.com/kiri8128/status/1603409391730163713?ref_src=twsrc%5Etfw">December 15, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

[^half_integer]: $2$ 倍すると整数になるような実数

# 問題例（ネタバレ注意）

## 問題例 1


<a href ="https://atcoder.jp/contests/abc087/tasks/arc090_b">問題</a>

元祖ポテンシャル UF と言えばこれですね。

<a href ="https://atcoder.jp/contests/abc087/submissions/37129172">AC コード</a>


## 問題例 2
<a href ="https://atcoder.jp/contests/past202109-open/tasks/past202109_m">問題</a>

オンラインで解くことができます。

<a href ="https://atcoder.jp/contests/past202109-open/submissions/37119145">AC コード</a>

## 問題例 3
<a href ="https://atcoder.jp/contests/typical90/tasks/typical90_bp">問題</a>

整数環の例です。本問では制約がやさしく値が確定することはありませんが、一般の場合でも解くことができます。

<a href ="https://atcoder.jp/contests/typical90/submissions/37130859">AC コード</a>


## 問題例 4
<a href ="https://atcoder.jp/contests/agc059/tasks/agc059_c">問題</a>

$\mathbb{Z}/2\mathbb{Z}$ の場合ですが、 $10^7$ オーダーになるので PyPy だと雑にやるとだめそうです。

<a href ="https://atcoder.jp/contests/agc059/submissions/37191393">TLE コード</a>

## 問題例 5
<a href ="https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Summer/2971">問題</a>

$\mathbb{Z}/p\mathbb{Z}$ が使えます。ライブラリ貼れば実装はめちゃくちゃ軽いですね。

<a href ="https://onlinejudge.u-aizu.ac.jp/status/users/Kiri8128/submissions/1/2971/judge/7163334/Python3">AC コード</a>



# 感想

求めるものや制約条件によってやりたいことが微妙に変わるので、どの問題にも対応できるように準備するのはわりと大変。ある程度網羅的に対応できる仕様にしたつもりだけど、あまり種類は多くないので個別に用意する手もあるかも？


# 関連ツイート

リプ等で情報くれたみなさんありがとうございました。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">【ゆる募】<br>（広義）ポテンシャル UF が使えそうな AtCoder の問題</p>&mdash; きり (@kiri8128) <a href="https://twitter.com/kiri8128/status/1601298851427946497?ref_src=twsrc%5Etfw">December 9, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">書きました。ツッコミどころがたくさんある気がするのでご意見お待ちしています。<br><br>-----<br>関係式付き Union Find <a href="https://t.co/FCJuc3nqkX">https://t.co/FCJuc3nqkX</a> <a href="https://twitter.com/hashtag/Qiita?src=hash&amp;ref_src=twsrc%5Etfw">#Qiita</a> <a href="https://twitter.com/kiri8128?ref_src=twsrc%5Etfw">@kiri8128</a>より</p>&mdash; きり (@kiri8128) <a href="https://twitter.com/kiri8128/status/1601634501528260609?ref_src=twsrc%5Etfw">December 10, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>