Day 037-Q3 | Virtual Tree + Steiner Tree on Tree

問題

$N$ 頂点、重み付き辺を持つ木。各クエリで頂点集合 $S_q$ が指定され、$S_q$ の全頂点を含む連結部分木の最小総辺重みを求める。

制約

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

$1 \le Q \le 10^5$

$\sum k_q \le 4 \times 10^5$

$1 \le w \le 10^9$

入出力例

入力例 1

出力例 1

12
9

概念図: Steiner Tree on Tree

DFS 訪問順にソートした $S$ の隣接ペア距離を巡回的に合計し、2 で割れば Steiner Tree の辺重み合計。

ヒント (段階的開示)

ヒント1: 方向性

木上の Steiner Tree は $S$ の DFS 訪問順ソート＋巡回的に隣接距離合計 ÷ 2 で求まる。

ヒント2: アプローチ

各クエリで S.sort(key=tin) → 距離合計 → // 2。距離は重み付き depth + LCA。

ヒント3: LCA O(1)

Euler Tour + Sparse Table で LCA を $O(1)$。前処理 $O(N \log N)$、クエリ全体 $O(\sum k_q)$。

模範解答 (Python)

import sys
from math import log2
input = sys.stdin.readline
sys.setrecursionlimit(1 << 25)

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

    tin = [0]*(N+1); depth_w = [0]*(N+1); depth_n = [0]*(N+1)
    euler = []; first = [0]*(N+1)
    stack = [(1, 0, 0, 0, 0)]; timer = 0
    while stack:
        v, p, dn, dw, state = stack.pop()
        if state == 0:
            tin[v] = timer; timer += 1
            depth_n[v] = dn; depth_w[v] = dw
            first[v] = len(euler)
            euler.append((dn, v))
            stack.append((v, p, dn, dw, 1))
            for (u, w) in G[v]:
                if u != p:
                    stack.append((u, v, dn+1, dw+w, 0))
        else:
            if p != 0:
                euler.append((dn-1, p))

    L = len(euler)
    LOG = max(1, int(log2(L)) + 1)
    st = [euler[:]]
    for k in range(1, LOG):
        prev = st[-1]; cur = []; step = 1 << (k-1)
        for i in range(L - (1<<k) + 1):
            a, b = prev[i], prev[i+step]
            cur.append(a if a[0] <= b[0] else b)
        st.append(cur)
    log_table = [0]*(L+1)
    for i in range(2, L+1):
        log_table[i] = log_table[i//2] + 1

    def lca(u, v):
        l, r = first[u], first[v]
        if l > r: l, r = r, l
        k = log_table[r - l + 1]
        a = st[k][l]; b = st[k][r - (1<<k) + 1]
        return (a if a[0] <= b[0] else b)[1]

    def dist(u, v):
        w = lca(u, v)
        return depth_w[u] + depth_w[v] - 2 * depth_w[w]

    Q = int(input())
    out = []
    for _ in range(Q):
        k = int(input())
        S = list(map(int, input().split()))
        S.sort(key=lambda x: tin[x])
        total = 0
        for i in range(k):
            a, b = S[i], S[(i+1) % k]
            total += dist(a, b)
        out.append(str(total // 2))
    sys.stdout.write('\n'.join(out) + '\n')

solve()

Step-by-Step 解説

1Steiner Tree on Tree の公式
$S$ を結ぶ最小部分木の辺重み合計 = $\frac{1}{2} \sum \text{dist}(s_i, s_{i+1 \bmod k})$（DFS順ソート後）。

2Euler Tour + Sparse Table
DFS で進入・退出時に頂点を記録した列を作り、深さの最小値で RMQ → LCA $O(1)$。

3クエリ処理
$S$ を tin 順にソート → 巡回隣接ペア距離合計 → ÷2。

4Virtual Tree への発展
辺重み以外のクエリ（パス上の集約 DP 等）が必要なら $S \cup \{\text{LCA(s_i, s_{i+1})}\}$ で頂点数 $O(k)$ の補助木を構築。

計算量

前処理: $O(N \log N)$（Sparse Table）
各クエリ: $O(k_q)$（LCA $O(1)$）
合計: $O(N \log N + \sum k_q)$

よくあるミス

ミス	原因	正しい書き方
`tin` でソートし忘れ	入力順のままだと公式が破綻	`S.sort(key=lambda v: tin[v])`
2 で割り忘れ	公式の係数を見落とす	最後に `total // 2`
LCA に重み無し depth を使う	木の辺重みを無視している	重み付き `depth_w` を使う
巡回的でない（最後と最初を結ばない）	cycle を閉じていない	`(i+1) % k` で巡回
再帰DFSでスタック溢れ	深い木で `RecursionError`	反復DFSに書き換え

次のステップ

発展: Virtual Tree 上で DP（パス上の集約・最大値・カウント）
応用: オンライン頂点追加に対応する動的 Steiner Tree
関連: 重心分解、HLD によるパスクエリ

自己評価

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

Day 037-Q3 — Virtual Tree（補助木）+ Steiner Tree on Tree

問題

制約