Day 067-Q3 — ポテンシャル法 Union-Find（重みつき DSU）

2026-06-20 赤色 Master / Phase 8+ ★★★★★★★★★ 重みつき Union-Find・差分制約系

問題

$N$ 頂点のグラフがある。以下の $Q$ 個のクエリを処理せよ。

  • クエリ型 1: 1 u v w — 「$A[v] - A[u] = w$」という関係を追加する。矛盾が生じる場合は conflict と出力せよ。
  • クエリ型 2: 2 u v — $A[v] - A[u]$ の値を求めよ。同一成分でない場合は unknown を出力せよ。

制約

パラメータ範囲
$N$$1 \le N \le 2 \times 10^5$
$Q$$1 \le Q \le 2 \times 10^5$
$|w|$$\le 10^9$
$u, v$$0 \le u, v < N$

入出力例

入力例 1

4 6
1 0 1 3
1 1 2 2
2 0 2
1 0 2 4
1 2 3 -1
2 0 3

出力例 1

5
conflict
4

A[1]-A[0]=3, A[2]-A[1]=2 → A[2]-A[0]=5。A[2]-A[0]=4 は矛盾。A[3]-A[2]=-1 → A[3]-A[0]=4。

概念図: ポテンシャル法の仕組み

ポテンシャル法 Union-Find の動作 Union 前（独立した2成分） root_u u pot[u]=wu root_v v pot[v]=wv pot[x] = A[x] - A[root(x)] Union 後（A[v]-A[u]=w を追加） root_v root_u pot[ru]=wv-wu-w u v pot[u]=wu (unchanged) ポテンシャル式の導出 A[v] - A[u] = w かつ A[u] = A[ru] + pot[u] = A[ru] + wu A[v] = A[rv] + pot[v] = A[rv] + wv => A[ru] - A[rv] = (A[v] - wv) - (A[u] - wu) = ... = wv - wu - w 差分クエリ: A[v] - A[u] = pot[v] - pot[u]（同一成分内） 矛盾検出: 同一成分で pot[v] - pot[u] ≠ w ならば conflict

ヒント（段階的開示）

ヒント1: 方向性
ポテンシャル法 Union-Find: 各ノードに「根までの重み差 pot[i] = A[i] - A[root(i)]」を管理する。パス圧縮時に差分を累積する。
ヒント2: アプローチ
  • pot[i]: $A[i] - A[\text{root}(i)]$ の値
  • find(x) でパス圧縮しながら pot[x] を根への差分に変換
  • union(u, v, w): $A[v] - A[u] = w$ を意味する。同一成分なら矛盾チェック
ヒント3: コード骨格 
def find(x):
    if parent[x] == x:
        return x
    root = find(parent[x])
    pot[x] += pot[parent[x]]  # 累積
    parent[x] = root
    return root

# クエリ型2: A[v] - A[u] = pot[v] - pot[u]
def diff(u, v):
    find(u); find(v)
    return pot[v] - pot[u]

模範解答 (Python)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(400010)

def main():
    N, Q = map(int, input().split())
    parent = list(range(N))
    rank = [0] * N
    pot = [0] * N  # pot[i] = A[i] - A[root(i)]

    def find(x):
        if parent[x] == x:
            return x
        root = find(parent[x])
        pot[x] += pot[parent[x]]
        parent[x] = root
        return root

    def weight(x):
        find(x)
        return pot[x]

    def union(u, v, w):
        # A[v] - A[u] = w
        wu = weight(u)
        wv = weight(v)
        ru = find(u)
        rv = find(v)
        if ru == rv:
            return pot[v] - pot[u] == w
        # pot[ru] = A[ru] - A[rv] = wv - wu - w
        if rank[ru] < rank[rv]:
            parent[ru] = rv
            pot[ru] = wv - wu - w
        elif rank[ru] > rank[rv]:
            parent[rv] = ru
            pot[rv] = wu - wv + w
        else:
            parent[rv] = ru
            pot[rv] = wu - wv + w
            rank[ru] += 1
        return True

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, u, v, w = line
            if not union(u, v, w):
                out.append('conflict')
        else:
            _, u, v = line
            ru = find(u)
            rv = find(v)
            if ru != rv:
                out.append('unknown')
            else:
                out.append(pot[v] - pot[u])

    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

Step 1: ポテンシャルの定義

pot[i] = A[i] - A[root(i)]。パス圧縮時に祖先のポテンシャルを累積することで、常に根への相対値を保持する。

Step 2: 差分クエリ

$A[v] - A[u] = (A[v] - A[\text{root}]) - (A[u] - A[\text{root}]) = \text{pot}[v] - \text{pot}[u]$（同一成分の場合）。

Step 3: Union 時のポテンシャル設定

$A[v] - A[u] = w$ かつ $A[u] = A[\text{ru}] + \text{wu}$, $A[v] = A[\text{rv}] + \text{wv}$ から:
$$A[\text{ru}] - A[\text{rv}] = \text{wv} - \text{wu} - w$$

Step 4: 矛盾検出

同一成分内に union(u, v, w) が来たとき、$\text{pot}[v] - \text{pot}[u] \neq w$ なら矛盾。

よくあるミス

ミス原因正しい書き方
パス圧縮順序ミス pot更新前にparentを書き換える root = find(parent[x]) の後に pot[x] += pot[parent[x]]
union時のpot符号ミス A[ru]-A[rv]とA[rv]-A[ru]を混同 式を紙で導出してから実装
再帰深度超過 N=2×10^5で連鎖union setrecursionlimit or iterative find

次のステップ

発展: 差分制約系（ベルマンフォード）との等価性を証明。関連: 重み付き DSU を用いた尺取り法・グラフ染色問題。

自己評価