Day 118-Q5 — 木分解上の動的計画法（Nice Tree Decomposition）

問題

N頂点M辺の無向グラフが与えられる。各頂点$i$には重み$w_i$がついている。さらに、このグラフの nice tree decomposition（整った木分解）が、T個のノードからなる操作列として与えられる。各ノードは次のいずれかである（番号は1-indexedで、子ノードの番号は必ず自分より小さい）。

• LEAF v: バッグ = {v}
• INTRO v p: バッグ = バッグ(p) ∪ {v}
• FORGET v p: バッグ = バッグ(p) \ {v}
• JOIN p q: バッグ = バッグ(p) = バッグ(q)

ノードTが根であり、バッグ(T)=∅であることが保証される。このグラフの最大重み独立集合の重みを求めよ。

入力形式

N M
w_1 w_2 ... w_N
u_1 v_1
...
u_M v_M
T
op_1
...
op_T

制約

入出力例

4 4
3 5 2 6
1 2
2 3
1 3
3 4
8
LEAF 1
INTRO 2 1
INTRO 3 2
FORGET 1 3
FORGET 2 4
INTRO 4 5
FORGET 3 6
FORGET 4 7

11

頂点2と頂点4を選ぶと5+6=11。頂点1,2,3は三角形なので同時に2つ以上選べない。

概念図: グラフと木分解、バッグDPの流れ

ヒント（段階的開示）

# dp[node] : dict, キー = バッグの部分集合(選んだ頂点の集合), 値 = そのときの最大重み
#
# LEAF v:      dp = { {}: 0, {v}: w[v] }
# INTRO v (子p): 子の各(S, val)について
#                dp[S] = val (vを選ばない)
#                S∪{v}がグラフ上で独立集合なら dp[S∪{v}] = val + w[v]
# FORGET v (子p): 子の各(S, val)について
#                dp[S\{v}] = max(既存の値, val)   # vを選んだ場合も選ばなかった場合もここで確定させる
# JOIN p, q (同じバッグ): 共通のSについて
#                dp[S] = dp_p[S] + dp_q[S] - (Sの頂点の重みの総和)  # 二重計上を引く
#
# 根(バッグが空集合)のdp[{}]が答え

模範解答 (Python)

📋 コピーimport sys


def solve():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it)); M = int(next(it))
    w = [0] + [int(next(it)) for _ in range(N)]
    edge_set = set()
    for _ in range(M):
        a = int(next(it)); b = int(next(it))
        edge_set.add((min(a, b), max(a, b)))
    T = int(next(it))

    dp = [None] * (T + 1)  # 1-indexed

    def is_indep(S):
        Sl = list(S)
        for i in range(len(Sl)):
            for j in range(i + 1, len(Sl)):
                a, b = Sl[i], Sl[j]
                if (min(a, b), max(a, b)) in edge_set:
                    return False
        return True

    for i in range(1, T + 1):
        typ = next(it)
        if typ == 'LEAF':
            v = int(next(it))
            dp[i] = {frozenset(): 0, frozenset({v}): w[v]}
        elif typ == 'INTRO':
            v = int(next(it)); p = int(next(it))
            src = dp[p]
            newdp = {}
            for S, val in src.items():
                if val > newdp.get(S, float('-inf')):
                    newdp[S] = val
                S2 = S | {v}
                if is_indep(S2):
                    cand = val + w[v]
                    if cand > newdp.get(S2, float('-inf')):
                        newdp[S2] = cand
            dp[i] = newdp
        elif typ == 'FORGET':
            v = int(next(it)); p = int(next(it))
            src = dp[p]
            newdp = {}
            for S, val in src.items():
                S2 = S - {v}
                if val > newdp.get(S2, float('-inf')):
                    newdp[S2] = val
            dp[i] = newdp
        elif typ == 'JOIN':
            p = int(next(it)); q = int(next(it))
            dl, dr = dp[p], dp[q]
            newdp = {}
            for S in dl:
                if S in dr:
                    wsum = sum(w[x] for x in S)
                    val = dl[S] + dr[S] - wsum
                    if val > newdp.get(S, float('-inf')):
                        newdp[S] = val
            dp[i] = newdp

    root_dp = dp[T]
    print(max(root_dp.values()) if root_dp else 0)


solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: 与えられた一般の木分解をnice tree decompositionへ自動変換するアルゴリズム自体を実装してみる。
• 次回予告: 次回セッションでのMaster Levelローテーション継続

自己評価

自分の回答

気づき・メモ