Day 058-Q2 — 木上のランダムウォーク期待値

問題

$N$ 頂点の根付き木（根 = 頂点 1）が与えられる。各辺に正の重み $w_e$ が付く。

頂点 $s$ から出発し、各ステップで現在の頂点に隣接する頂点の 1 つを辺の重みに比例した確率で選んで移動する。

• クエリ 1 s t: 頂点 $s$ から初めて頂点 $t$ に到達するまでのステップ数の期待値
• クエリ 2 s: 頂点 $s$ から根（頂点 1）に到達するまでのステップ数の期待値

入出力例

4 2
1 2 1
2 3 2
2 4 1
2 1
2 3

4.000000000
6.666666667

頂点 2 の隣接: 1(重み1), 3(重み2), 4(重み1) → 合計重み 4。
頂点 2 → 1 の確率 = 1/4, 2→3 の確率 = 2/4, 2→4 の確率 = 1/4。

概念図: 木上ランダムウォークと調和関数

ヒント（段階的開示）

# パスを取得してガウス消去
def get_path(s, t, parent, depth):
    path_s, path_t = [s], [t]
    u, v = s, t
    while depth[u] > depth[v]:
        u = parent[u]
        path_s.append(u)
    while depth[v] > depth[u]:
        v = parent[v]
        path_t.append(v)
    while u != v:
        u, v = parent[u], parent[v]
        path_s.append(u)
        path_t.append(v)
    if path_s[-1] == path_t[-1]:
        return path_s + path_t[-2::-1]
    return path_s + path_t[::-1]

# 連立方程式 h[v] = 1 + Σ p_vu * h[u] をガウス消去で解く

模範解答 (Python)

コピーimport sys
from collections import defaultdict, deque
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    depth = [0] * (N + 1)
    parent = [0] * (N + 1)
    visited = [False] * (N + 1)
    visited[1] = True
    q = deque([1])
    while q:
        v = q.popleft()
        for u, w in graph[v]:
            if not visited[u]:
                visited[u] = True
                depth[u] = depth[v] + 1
                parent[u] = v
                q.append(u)

    def get_path(s, t):
        path_s, path_t = [s], [t]
        u, v = s, t
        while depth[u] > depth[v]:
            u = parent[u]; path_s.append(u)
        while depth[v] > depth[u]:
            v = parent[v]; path_t.append(v)
        while u != v:
            u = parent[u]; v = parent[v]
            path_s.append(u); path_t.append(v)
        if path_s[-1] == path_t[-1]:
            return path_s + path_t[-2::-1]
        return path_s + path_t[::-1]

    def expected_steps(s, t):
        path = get_path(s, t)
        n = len(path)
        if n == 1:
            return 0.0
        W = {v: sum(w for _, w in graph[v]) for v in path}
        path_set = set(path)
        idx = {v: i for i, v in enumerate(path)}
        size = n - 1
        A = [[0.0] * size for _ in range(size)]
        b = [0.0] * size
        for i in range(size):
            v = path[i]
            wv = W[v]
            A[i][i] = 1.0
            b[i] = 1.0
            for u, w in graph[v]:
                p = w / wv
                if u == path[-1]:
                    pass
                elif u in idx:
                    j = idx[u]
                    if j < size:
                        A[i][j] -= p
                else:
                    total_w = sum(ww for _, ww in graph[u])
                    b[i] += p * (2.0 * total_w / w + 1)
        for col in range(size):
            pivot = next((row for row in range(col, size) if abs(A[row][col]) > 1e-12), -1)
            if pivot == -1:
                continue
            A[col], A[pivot] = A[pivot], A[col]
            b[col], b[pivot] = b[pivot], b[col]
            for row in range(size):
                if row != col and abs(A[row][col]) > 1e-12:
                    f = A[row][col] / A[col][col]
                    for k in range(size):
                        A[row][k] -= f * A[col][k]
                    b[row] -= f * b[col]
        h = [b[i] / A[i][i] for i in range(size)]
        return h[0]

    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            s, t = int(line[1]), int(line[2])
            print(f"{expected_steps(s, t):.9f}")
        else:
            s = int(line[1])
            print(f"{expected_steps(s, 1):.9f}")

main()

Step-by-Step 解説

Step 1: 調和関数の定式化

期待ステップ数 $h[v]$ は調和関数: $$h[v] = 1 + \sum_{u \sim v} P(v \to u) h[u]$$ 境界条件 $h[t]=0$。

Step 2: 木パス上の連立方程式

木では $s \to t$ のパスは一意。パス上の頂点のみ未知数とし、パス外はすぐに戻ってくる commute time で補正する。

Step 3: ガウス消去で解く

パス長 $L$ として $O(L^2)$ のガウス消去。$L \le N$ なので最悪 $O(N^2)$。

Step 4: Commute Time の公式

無向グラフでの commute time（往復期待値）= $2 \times$ 総辺重み合計 $\times$ 有効抵抗。

よくあるミス

次のステップ

発展問題: $s$ から出発してすべての頂点を訪問するまでの期待ステップ数（Cover Time）を効率的に計算せよ。

自己評価