概要

根付き木上で「パス上の全辺に \(+1\) する更新」を \(Q\) 回行った後、「パス上の辺の重みの最小値」を求めるクエリに \(R\) 回答える問題です。

考察

素朴なアプローチの問題点

パス更新を愚直に行うと、1回の更新で最大 \(O(N)\) 本の辺を更新するため、全体で \(O(NQ)\) かかります。同様にクエリも愚直にパスを辿ると \(O(NR)\) です。\(N, Q, R \leq 5 \times 10^4\) なので、各操作を効率化する必要があります。

重要な気づき

更新の効率化：差分配列（Euler Tour + 差分）

木のパス上に一様に値を加算する操作は、ノード上の差分配列で効率的に処理できます。辺 \(i\)（都市 \(i\) とその親を結ぶ）の加算回数は、都市 \(i\) の部分木に含まれるノードの差分値の合計に等しくなります。

具体的には、パス \(u \to v\)（LCAを \(l\) とする）に対して： - \(\text{diff}[u] += 1\) - \(\text{diff}[v] += 1\) - \(\text{diff}[l] -= 2\)

と記録し、最後にボトムアップで部分木の合計を求めると、\(\text{diff}[i]\) が辺 \(i\) に加算された回数になります。

クエリの効率化：ダブリング（Binary Lifting）による最小値

パス上の最小値クエリは、LCAを利用したダブリングによるパス最小値で \(O(\log N)\) で処理できます。

アルゴリズム

ステップ1：前処理（LCA用ダブリング）

• BFSで各ノードの深さ \(\text{depth}[i]\) を計算
• ダブリングテーブル \(\text{up}[k][i]\)：ノード \(i\) から \(2^k\) 回親を辿った先の祖先

ステップ2：パス更新（差分配列）

各更新 \((u_j, v_j)\) に対し： 1. LCA \(l = \text{lca}(u_j, v_j)\) を求める 2. \(\text{diff}[u_j] += 1,\ \text{diff}[v_j] += 1,\ \text{diff}[l] -= 2\)

全更新後、BFS逆順（葉→根）に \(\text{diff}[\text{parent}] += \text{diff}[\text{child}]\) と集約すると、\(\text{diff}[i]\) が辺 \(i\) の加算回数になります。

最終的な辺 \(i\) の重み：\(\text{edge\_w}[i] = W_i + \text{diff}[i]\)

ステップ3：クエリ応答（ダブリングによるパス最小値）

• \(\text{up\_min}[k][i]\)：ノード \(i\) から \(2^k\) 本の辺を上に辿る間の辺の重みの最小値
• 基底：\(\text{up\_min}[0][i] = \text{edge\_w}[i]\)
• 遷移：\(\text{up\_min}[k][i] = \min(\text{up\_min}[k-1][i],\ \text{up\_min}[k-1][\text{up}[k-1][i]])\)

クエリ \((a, b)\) では、LCAを求めるのと同じ要領で \(a \to \text{LCA}\) と \(b \to \text{LCA}\) の2本のパスに分割し、ダブリングで最小値を集めます。

計算量

• 時間計算量: \(O((N + Q + R) \log N)\)
  • 前処理（ダブリングテーブル構築）：\(O(N \log N)\)
  • 各更新のLCA計算：\(O(Q \log N)\)
  • 差分の集約：\(O(N)\)
  • 各クエリの応答：\(O(R \log N)\)
• 空間計算量: \(O(N \log N)\)（ダブリングテーブル2つ分）

実装のポイント

• 差分配列のトリック：辺に対する加算を「LCAで \(-2\)、両端で \(+1\)」としてノードに記録し、部分木合計で辺への加算回数を復元する。これは木上のimos法とも呼ばれます。

• ボトムアップの集約：BFS順の逆順に処理すれば、葉から根へ正しく集約できます（再帰だとスタックオーバーフローの恐れがあるため反復で処理）。

• \(\text{up}[k][0] = 0\)（根の親は存在しないので \(0\)）としておくことで、LCA計算時に深さを揃える際に範囲外参照を防ぎます。

• 答えが \(2^{63}-1\) 以下とあるため、64bit整数（Pythonでは自動的に多倍長）で問題なく処理できます。

  ソースコード

import sys
from math import log2

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    
    N = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    W = [0] * (N + 1)  # W[i] = weight of edge i (edge between i and parent[i])
    children = [[] for _ in range(N + 1)]
    
    for i in range(2, N + 1):
        p = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        parent[i] = p
        W[i] = w
        children[p].append(i)
    
    # BFS to compute depth and euler tour
    depth = [0] * (N + 1)
    order = []
    stack = [1]
    visited = [False] * (N + 1)
    visited[1] = True
    # Iterative BFS
    from collections import deque
    q = deque([1])
    while q:
        u = q.popleft()
        order.append(u)
        for c in children[u]:
            depth[c] = depth[u] + 1
            visited[c] = True
            q.append(c)
    
    # Binary lifting for LCA
    LOG = max(1, (N).bit_length())
    up = [[0] * (N + 1) for _ in range(LOG)]
    for i in range(1, N + 1):
        up[0][i] = parent[i]
    for k in range(1, LOG):
        for i in range(1, N + 1):
            up[k][i] = up[k-1][up[k-1][i]]
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1:
                u = up[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]
                v = up[k][v]
        return up[0][u]
    
    # Process updates: for each update (u, v), add 1 to all edges on path u->v
    # Use difference array on nodes: for edge i (connecting i to parent[i]),
    # the edge weight increase = diff[i] where diff is accumulated.
    # For path u->v with LCA l: diff[u] += 1, diff[v] += 1, diff[l] -= 2
    
    diff = [0] * (N + 1)
    
    Q = int(input_data[idx]); idx += 1
    for _ in range(Q):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        if u == v:
            continue
        l = lca(u, v)
        diff[u] += 1
        diff[v] += 1
        diff[l] -= 2
    
    # Compute subtree sums in reverse BFS order (bottom-up)
    for node in reversed(order):
        for c in children[node]:
            diff[node] += diff[c]
    
    # Now diff[i] for i>=2 is the number of times edge i was incremented
    # Final weight of edge i = W[i] + diff[i]
    edge_w = [0] * (N + 1)
    for i in range(2, N + 1):
        edge_w[i] = W[i] + diff[i]
    
    # Now answer queries: for each query (a, b), find min edge weight on path a->b
    # With N, R up to 5*10^4, we can use binary lifting with sparse table for min
    # up_min[k][i] = min edge weight on the path of 2^k edges going up from i
    
    up_min = [[float('inf')] * (N + 1) for _ in range(LOG)]
    for i in range(1, N + 1):
        if parent[i] != 0:
            up_min[0][i] = edge_w[i]
        else:
            up_min[0][i] = float('inf')
    for k in range(1, LOG):
        for i in range(1, N + 1):
            up_min[k][i] = min(up_min[k-1][i], up_min[k-1][up[k-1][i]])
    
    def query_min(u, v):
        if u == v:
            return 0
        res = float('inf')
        if depth[u] < depth[v]:
            u, v = v, u
        diff_d = depth[u] - depth[v]
        for k in range(LOG):
            if (diff_d >> k) & 1:
                res = min(res, up_min[k][u])
                u = up[k][u]
        if u == v:
            return res
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                res = min(res, up_min[k][u], up_min[k][v])
                u = up[k][u]
                v = up[k][v]
        res = min(res, up_min[0][u], up_min[0][v])
        return res
    
    R = int(input_data[idx]); idx += 1
    out = []
    for _ in range(R):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        out.append(str(query_min(a, b)))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。