Day 043-Q4 | Laminar Family・ラミナー木 DP（独立集合）

問題

$N$ 個の区間 $[l_i, r_i]$（$1 \le l_i \le r_i \le M$）はラミナー族（任意の 2 区間は包含または互いに素）をなす。各区間 $i$ にコスト $c_i > 0$ が付いている。祖先-子孫関係にある区間を同時に選べないという制約のもとで、コスト総和を最大化せよ。

制約

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

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

$1 \le c_i \le 10^9$

入力はラミナー族を保証

時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

出力例 1

選択: [1,2](6) + [3,5](2) + [6,10](4) = 12

概念図: ラミナー木の構造と独立集合 DP

ヒント（段階的開示）

ヒント1: 方向性

ラミナー族は自然に木構造をなす。区間の包含関係を親子関係とし、互いに素な区間を兄弟とする木を構築する。この木上の独立集合問題（祖先-子孫関係の同時選択禁止）は木 DP で $O(N)$ に解ける。

ヒント2: アプローチ

区間を左端昇順・右端降順でソート
スタックを使い $O(N)$ でラミナー木を構築
木 DP: dp[v][0] = $v$ を選ばない最大、dp[v][1] = $v$ を選ぶ最大
遷移: 子 $c$ に対して dp[v][0] += max(dp[c][0], dp[c][1])、dp[v][1] += dp[c][0]

ヒント3: 実装骨格

# ソート: 左端昇順、同じなら右端降順（大きい区間が先）
intervals.sort(key=lambda x: (x[0], -x[1]))

# スタックで親子関係を構築
stack = [(0, M, ROOT)]  # 仮想根で全体を包含
for l, r, c in intervals:
    while not (stack[-1][0] <= l and r <= stack[-1][1]):
        stack.pop()
    children[stack[-1][2]].append(current)
    stack.append((l, r, current))

# 木 DP（トポロジカル順: 葉→根）
for v in reversed(topo_order):
    dp[v][1] = cost[v]
    for c in children[v]:
        dp[v][0] += max(dp[c][0], dp[c][1])
        dp[v][1] += dp[c][0]

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    intervals = []
    for i in range(N):
        l, r, c = map(int, input().split())
        intervals.append((l, r, c, i))

    ROOT = N
    cost = [0] * (N + 1)
    for i, (l, r, c, _) in enumerate(intervals):
        cost[i] = c

    intervals.sort(key=lambda x: (x[0], -x[1]))

    children = [[] for _ in range(N + 1)]
    stack = [(0, M + 1, ROOT)]  # 仮想根

    for l, r, c, orig in intervals:
        while not (stack[-1][0] <= l and r <= stack[-1][1]):
            stack.pop()
        children[stack[-1][2]].append(orig)
        stack.append((l, r, orig))

    # トポロジカル順（DFS後順）
    order = []
    stk = [ROOT]
    while stk:
        v = stk.pop()
        order.append(v)
        for ch in children[v]:
            stk.append(ch)
    order.reverse()

    dp = [[0, 0] for _ in range(N + 1)]
    for v in order:
        if v != ROOT:
            dp[v][1] = cost[v]
        for ch in children[v]:
            dp[v][0] += max(dp[ch][0], dp[ch][1])
            dp[v][1] += dp[ch][0]

    print(max(dp[ROOT][0], dp[ROOT][1]))

solve()

Step-by-Step 解説

1ラミナー族とは
任意の 2 集合 A, B に対して「A ⊆ B」「B ⊆ A」「A ∩ B = ∅」の 3 通りのいずれかが成り立つ集合族。区間で言うと包含か互いに素。この性質が木構造への変換を可能にする。

2木構築（スタック法）
区間を左端昇順・右端降順でソートすると、スタックのトップが「現在の区間の最小包含区間（親）」になる。親子関係を O(N) で決定できる。

3木上の独立集合 DP
dp[v][0] = $v$ を選ばない場合の部分木最大値（子は自由）
dp[v][1] = $v$ を選ぶ場合（子はすべて選ばない）
遷移は葉から根の方向に処理。

4計算量の導出
ソート $O(N \log N)$、木構築 $O(N)$、DP $O(N)$。合計 $O(N \log N)$。

計算量

ソート: $O(N \log N)$
ラミナー木構築: $O(N)$（スタック法）
木 DP: $O(N)$
空間: $O(N)$

よくあるミス

ミス	原因	正しい書き方
仮想根の区間が小さすぎる	全区間を包含できるサイズが必要	`(0, M+1, ROOT)` などで全体を包含
スタックポップ条件の誤り	互いに素な判定ミス	`not (stack[-1][0] <= l and r <= stack[-1][1])`
DP の初期化で cost を dp[v][1] に入れ忘れ	ROOT のみコスト0	各ノード `dp[v][1] = cost[v]`
トポロジカル順を葉→根にしていない	子の dp が未計算	DFS後順（逆順）で処理

次のステップ

発展問題: ラミナー族の最小コスト被覆（すべての葉を被覆する最小コスト選択）
類題: CF 1239D "Catowice City"、ICPC Regionals ラミナー族問題
応用: ネットワーク設計・階層的クラスタリング

自己評価

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