Day 010-Q4 | Phase 6 総復習

問題

$N$ ノードの根付き木、値 $V[i]$。以下の $Q$ 個のクエリを処理せよ。

1 u v : $u$ と $v$ のパス上の全ての値を +1（LCA 利用）
2 u k : $u$ の部分木に含まれる値の中で $k$ 番目に小さい値を答える

制約

$1 \le N \le 5000$

$1 \le Q \le 5000$

$1 \le V[i] \le 10^9$

根はノード 1

入出力例

入力例 1

出力例 1

6
2

ヒント (段階的開示)

ヒント1: 方向性

LCA・オイラーツアー・クイックセレクトの組み合わせ。

ヒント2: アプローチ

$N, Q \le 5000$ なので $O(QN)$ で通る。LCA は朴素 $O(N)$、部分木は in/out time で連続区間として扱う。

ヒント3: 誘導

部分木 $u$ = in_t[u] <= in_t[v] <= out_t[u] となる $v$ の集合。

模範解答 (Python)

import sys
from collections import defaultdict
import random
input = sys.stdin.readline
sys.setrecursionlimit(200000)

def solve():
    N, Q = map(int, input().split())
    V = [0] + list(map(int, input().split()))

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

    parent = [0] * (N+1)
    depth = [0] * (N+1)
    in_t = [0] * (N+1)
    out_t = [0] * (N+1)
    order = []

    timer = [0]
    stack = [(1, 0, False)]
    while stack:
        node, par, leaving = stack.pop()
        if leaving:
            out_t[node] = timer[0]
            continue
        parent[node] = par
        in_t[node] = timer[0]
        timer[0] += 1
        order.append(node)
        stack.append((node, par, True))
        for child in adj[node]:
            if child != par:
                depth[child] = depth[node] + 1
                stack.append((child, node, False))

    def lca(u, v):
        while depth[u] > depth[v]: u = parent[u]
        while depth[v] > depth[u]: v = parent[v]
        while u != v: u = parent[u]; v = parent[v]
        return u

    def path_nodes(u, v):
        l = lca(u, v)
        nodes = []
        x = u
        while x != l: nodes.append(x); x = parent[x]
        nodes.append(l)
        y = v
        while y != l: nodes.append(y); y = parent[y]
        return nodes

    def subtree_values(u):
        return [V[node] for node in order if in_t[u] <= in_t[node] <= out_t[u]]

    def quickselect(arr, k):
        if len(arr) == 1: return arr[0]
        pivot = random.choice(arr)
        lo = [x for x in arr if x < pivot]
        mid = [x for x in arr if x == pivot]
        hi = [x for x in arr if x > pivot]
        if k <= len(lo): return quickselect(lo, k)
        elif k <= len(lo) + len(mid): return pivot
        else: return quickselect(hi, k - len(lo) - len(mid))

    results = []
    for _ in range(Q):
        tokens = list(map(int, input().split()))
        if tokens[0] == 1:
            _, u, v = tokens
            for node in path_nodes(u, v):
                V[node] += 1
        else:
            _, u, k = tokens
            vals = subtree_values(u)
            results.append(quickselect(vals, k))

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

solve()

Step-by-Step 解説

1オイラーツアー
DFS で in_t / out_t を付与。部分木 = 連続区間として表現。

2LCA の朴素実装
depth が深い方を上に引き上げ、両者一致まで親を辿る。$N \le 5000$ なら十分。

3パス上ノード列挙
$u$ から LCA、$v$ から LCA。LCA を1回だけ追加。

よくあるミス

ミス	原因	正しい書き方
out_time の設定忘れ	in_time だけでは部分木判定不可	DFS 退出時に out_time を記録
LCA が根を超える	depth 比較順ミス	depth の大きい方から合わせる
パスの重複ノード	u=LCA のケース	LCA を 1 回だけ追加

次のステップ

発展問題: $N, Q \le 10^5$ なら binary lifting + セグ木で $O(Q \log N)$

自己評価

完全理解おおむね理解要復習

Day 010-Q4 — Phase 6 総復習（複合問題）

問題

制約