Day 056-Q5 — 重みつきランダムスパニングツリー（行列木定理・有効抵抗）

問題

$N$ 頂点 $M$ 辺の無向重み付きグラフ $G$（各辺 $e_k = (u_k, v_k, w_k)$）に対して:

1. 全スパニングツリーの重み総和 $\mathcal{Z} = \sum_T \prod_{e \in T} w_e$ を $\bmod 998244353$ で出力
2. 各辺 $e_k$ が重みに比例したランダムスパニングツリーに含まれる確率 $\Pr[e_k \in T] = w_k \cdot R_k \bmod 998244353$ を出力

入出力例

3 3
1 2 2
2 3 3
1 3 6

42
570312517 998244351 1

$\mathcal{Z} = w_{12} \cdot w_{23} + w_{12} \cdot w_{13} + w_{23} \cdot w_{13} = 6 + 12 + 18 = 36$（実際の入力値で確認してください）。
各辺の有効抵抗 $R_k$ を求め $w_k \cdot R_k \bmod p$ が各辺の選択確率。

概念図: キルヒホッフ行列木定理と有効抵抗

ヒント（段階的開示）

def mat_det(A, n, mod):
    A = [row[:] for row in A]
    det = 1
    for col in range(n):
        pivot = next((r for r in range(col, n) if A[r][col] % mod != 0), -1)
        if pivot == -1: return 0
        if pivot != col:
            A[col], A[pivot] = A[pivot], A[col]
            det = mod - det
        det = det * A[col][col] % mod
        inv = pow(A[col][col], mod-2, mod)
        for row in range(col+1, n):
            if A[row][col] == 0: continue
            f = A[row][col] * inv % mod
            for k in range(col, n):
                A[row][k] = (A[row][k] - f*A[col][k]) % mod
    return det

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline
MOD = 998244353

def solve():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        edges.append((u-1, v-1, w % MOD))

    # 重み付きラプラシアン
    L = [[0]*N for _ in range(N)]
    for u, v, w in edges:
        L[u][u] = (L[u][u] + w) % MOD
        L[v][v] = (L[v][v] + w) % MOD
        L[u][v] = (L[u][v] - w) % MOD
        L[v][u] = (L[v][u] - w) % MOD

    Lp = [[L[i+1][j+1] for j in range(N-1)] for i in range(N-1)]

    def mat_det(A, n):
        A = [row[:] for row in A]
        det = 1
        for col in range(n):
            pivot = -1
            for row in range(col, n):
                if A[row][col] % MOD != 0:
                    pivot = row; break
            if pivot == -1: return 0
            if pivot != col:
                A[col], A[pivot] = A[pivot], A[col]
                det = MOD - det
            inv_p = pow(A[col][col], MOD-2, MOD)
            det = det * A[col][col] % MOD
            for row in range(col+1, n):
                if A[row][col] == 0: continue
                f = A[row][col] * inv_p % MOD
                for k in range(col, n):
                    A[row][k] = (A[row][k] - f*A[col][k]) % MOD
        return det % MOD

    Z = mat_det(Lp, N-1)
    print(Z)

    invN = pow(N, MOD-2, MOD)
    Lreg = [[L[i][j] for j in range(N)] for i in range(N)]
    for i in range(N):
        for j in range(N):
            Lreg[i][j] = (Lreg[i][j] + invN) % MOD

    def mat_inv(A, n):
        A = [row[:] + [1 if i==j else 0 for j in range(n)] for i, row in enumerate(A)]
        for col in range(n):
            pivot = -1
            for row in range(col, n):
                if A[row][col] % MOD != 0:
                    pivot = row; break
            if pivot == -1: return None
            A[col], A[pivot] = A[pivot], A[col]
            inv_p = pow(A[col][col], MOD-2, MOD)
            for k in range(2*n): A[col][k] = A[col][k]*inv_p%MOD
            for row in range(n):
                if row == col or A[row][col] == 0: continue
                f = A[row][col]
                for k in range(2*n):
                    A[row][k] = (A[row][k] - f*A[col][k]) % MOD
        return [[A[i][j+n] for j in range(n)] for i in range(n)]

    inv_Lreg = mat_inv(Lreg, N)
    Lplus = [[(inv_Lreg[i][j] - invN) % MOD for j in range(N)] for i in range(N)]

    results = []
    for u, v, w in edges:
        R = (Lplus[u][u] + Lplus[v][v] - 2*Lplus[u][v]) % MOD
        prob = w * R % MOD
        results.append(str(prob))

    print(*results)

solve()

Step-by-Step 解説

Step 1: 重み付きラプラシアンの構成

$L_{uu} = \sum_{e \ni u} w_e$（次数の重み和）、$L_{uv} = -w_{uv}$（辺があれば負の重み）。対角優位行列。

Step 2: 行列木定理

$\mathcal{Z} = \det(L')$。$L'$ は任意の1行1列を除いた $(N-1) \times (N-1)$ 行列。ガウス消去で $O(N^3)$。

Step 3: 擬似逆行列 $L^+$ の計算

$(L + \frac{1}{N}J)$ は正則行列（ラプラシアンに一様行列を加えてランクを $N$ に）。その逆行列から $\frac{1}{N}J$ を引くと $L^+$。

Step 4: 有効抵抗と確率

電気ネットワーク理論: 辺 $(u, v, w)$ に抵抗 $1/w$ を割り当てたとき、$u$-$v$ 間の有効抵抗は $R_{uv} = L^+_{uu} + L^+_{vv} - 2L^+_{uv}$。$\Pr[e \in T] = w_e \cdot R_e$。

計算量

よくあるミス

次のステップ

• Wilson's Algorithm（LERW）: ランダムスパニングツリーを直接サンプリング $O(N^3)$
• 有効抵抗によるグラフスペクトル解析・電気ネットワーク
• スペクトルグラフ理論: ラプラシアン固有値と連結性

自己評価