Day 033-Q2 | 木上の積DP・モジュラー逆元

問題

$N$ 頂点の根付き木（根 = 頂点1）と各辺の重み $w$ が与えられる。$Q$ 個のクエリ $(v_k, x_k)$ に対し、辺 $(v_k, \text{parent}(v_k))$ の重みを $x_k$ に変更したときの全辺積を $10^9+7$ で割った余りで答えよ。各クエリは独立。

入力形式

N
u_1 v_1 w_1
...
u_{N-1} v_{N-1} w_{N-1}
Q
v_1 x_1
...
v_Q x_Q

制約

$2 \le N \le 2 \times 10^5$

$1 \le w_i, x_k \le 10^9$

$1 \le Q \le 2 \times 10^5$

$v_k$ は根以外

入出力例

入力例 1

出力例 1

280
350
180

ヒント (段階的開示)

ヒント1: 方向性

全辺積 $P$ を事前計算。辺重み変更後の積は $P \cdot w_e^{-1} \cdot x$。逆元は mod 逆元で。

ヒント2: アプローチ

フェルマーの小定理: $w^{-1} \equiv w^{p-2} \pmod p$。pow(w, MOD-2, MOD) で $O(\log p)$。

ヒント3: 誘導

MOD = 10**9 + 7
P = 1
for w in weights: P = P * w % MOD
for v, x in queries:
    w_e = parent_edge_w[v]
    ans = P * pow(w_e, MOD-2, MOD) % MOD * x % MOD

模範解答 (Python)

import sys
from collections import defaultdict, deque

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1

    MOD = 10**9 + 7

    graph = defaultdict(list)
    raw_edges = []
    for _ in range(N - 1):
        u, v, w = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
        graph[u].append(v)
        graph[v].append(u)
        raw_edges.append((u, v, w))

    parent = [-1] * (N + 1)
    parent_edge_w = [0] * (N + 1)
    visited = [False] * (N + 1)
    queue = deque([1])
    visited[1] = True
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                queue.append(v)

    for u, v, w in raw_edges:
        if parent[v] == u:
            parent_edge_w[v] = w
        else:
            parent_edge_w[u] = w

    P = 1
    for i in range(2, N + 1):
        P = P * parent_edge_w[i] % MOD

    Q = int(data[idx]); idx += 1
    results = []
    for _ in range(Q):
        v, x = int(data[idx]), int(data[idx+1]); idx += 2
        w_e = parent_edge_w[v]
        ans = P * pow(w_e, MOD - 2, MOD) % MOD * x % MOD
        results.append(ans)

    sys.stdout.write('\n'.join(map(str, results)) + '\n')

solve()

Step-by-Step 解説

1木の根付き化
BFS で各頂点の parent と parent_edge_w を決定。

2全辺積の事前計算
$P = \prod_{v=2}^{N} \text{parent\_edge\_w}[v] \bmod (10^9+7)$。

3モジュラー逆元
$w_e^{-1} \equiv w_e^{p-2} \pmod p$（フェルマーの小定理）。pow(w_e, MOD-2, MOD) で $O(\log p)$。

4クエリ応答
$\text{ans} = P \cdot w_e^{-1} \cdot x \bmod (10^9+7)$。

計算量

前処理: $O(N)$
各クエリ: $O(\log p)$
全体: $O(N + Q \log p)$

よくあるミス

ミス	原因	正しい書き方
辺を親子どちらに紐付けるか不明	無向辺	BFS で `parent[v]` を決定後に判定
`w = 0` で逆元未定義	$0^{-1}$ は存在しない	制約 $w \ge 1$ を確認
掛け算で `% MOD` 漏れ	意図せず巨大数	明示的に各演算で `% MOD`
クエリが累積すると誤解	独立クエリ	毎回元の $P$ から計算

Day 033-Q2 — 木上の積DP・モジュラー逆元（Tree Product DP + Modular Inverse）

問題