Day 112-Q4 — 木上の最大重みマッチング（Tree DP・O(N)厳密解法）

2026-08-04 赤色 Master / Phase 8+ ★★★★★★★★★ dp/dp0の合成による木DP

問題

$N$頂点の木があり、$i$番目の辺は頂点$u_i,v_i$を結び重み$w_i$を持つ。辺の集合$M$であってどの2本も共通の頂点を持たない（マッチング）ものの中で、重みの総和が最大になるものを選び、その最大値を出力せよ。

入力形式

N
u_1 v_1 w_1
...
u_{N-1} v_{N-1} w_{N-1}

制約

$2 \le N \le 2\times10^5$
$1 \le w_i \le 10^9$
与えられるグラフは木

入出力例

入力例1

6
1 2 3
1 3 6
3 4 5
3 5 4
2 6 2

出力例1

8

辺1-3(重み6)と辺2-6(重み2)を選ぶと頂点が重複せず合計8が最大。辺1-2(3)と辺3-4(5)の組も合計8で同着だがそれ以上は作れない。

概念図: dp（自由）とdp0（未使用強制）を合成する

dp[v] = max(dp0[v], dp0[v] + max_j(w_j + dp0[c_j] - dp[c_j])) v c1 c2 c3 vはc2とマッチ c1,c3は dp[ci] のまま（自由に最適化） / c2だけ dp0[c2]（未使用強制）を使う

ヒント（段階的開示）

ヒント1: 方向性
一般グラフの最大重みマッチングはBlossom Algorithmが必要だが、対象が木なら根から葉への木DPだけでO(N)で厳密に解ける。各頂点が「どれかの辺にマッチしているか」を状態として持つ。
ヒント2: アプローチ
$dp[v]$=部分木vの最大マッチング（vはマッチしてもしなくてもよい）、$dp0[v]$=vが未使用と制約した場合の最大マッチング。$dp0[v]=\sum dp[c_i]$。$dp[v]=\max(dp0[v], \max_j(w_j+dp0[c_j]+\sum_{i\neq j}dp[c_i]))$。差分$w_j+dp0[c_j]-dp[c_j]$の最大値をdp0[v]に足すだけでO(N)で計算できる。
ヒント3: 誘導（コード骨格） 
s = sum(dp[c] for c in children)
dp0[v] = s
best_extra = 0
for c in children:
    extra = w(v,c) + dp0[c] - dp[c]
    best_extra = max(best_extra, extra)
dp[v] = s + best_extra

模範解答 (Python)

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1

    g = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        g[u].append((v, w))
        g[v].append((u, w))

    parent = [0] * (N + 1)
    pw = [0] * (N + 1)
    order = []
    visited = [False] * (N + 1)
    stack = [1]
    visited[1] = True
    while stack:
        u = stack.pop()
        order.append(u)
        for v, w in g[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                pw[v] = w
                stack.append(v)

    dp = [0] * (N + 1)
    dp0 = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    for v in order:
        if parent[v] != 0:
            children[parent[v]].append(v)

    for u in reversed(order):
        s = 0
        for c in children[u]:
            s += dp[c]
        dp0[u] = s
        best_extra = 0
        for c in children[u]:
            extra = pw[c] + dp0[c] - dp[c]
            if extra > best_extra:
                best_extra = extra
        dp[u] = s + best_extra

    print(dp[1])

main()
計算量: iterative DFS前処理$O(N)$、post-order DP$O(N)$、全体$O(N)$。$N\le9$の全マッチング列挙による厳密解（300ケース）との突き合わせで全て一致することを確認済み。

Step-by-Step 解説

1状態設計の理由
「vを含む部分木の最大値」だけでは親がvを使いたいときに判定できないため、dp0（未使用強制）を別に持つ。
2子をすべて自由にした場合を基準にする
dp0[v]は「vを使わない」場合の値であり、dp[v]の下限でもある。
31本だけ辺を使う場合を差分で評価する
vをc_jにマッチさせるとc_j側はdp0[c_j]を使う必要があり、他の子は影響を受けない。この差分を1項にまとめてO(N)で計算する。
4最大1本しか選べないことの正当性
頂点は同時に2本以上の辺にマッチできないため「子のうちどれか高々1つ」で全可能性を尽くしている。
5post-orderで葉から根へ計算する
iterative DFSの訪問順を逆順にたどれば子が親より先に確定する。

よくあるミス

ミス原因正しい書き方
dp[v]だけを持ちdp0[v]を省略する「部分木の最大値」だけで十分だと誤解する親がvを使う場合の制約表現にdp0が必須
vを2本以上の子にマッチさせられると誤って多重加算するbest_extraの計算がsumになっている差分の最大値1つだけをdp0[v]に加える（maxであってsumではない）
差分が負になりうることを見落とし常に加算するdp0[c]<=dp[c]より差分が負になるケースを考慮しないbest_extraの初期値を0にし負の差分は採用しない
再帰DFSで実装しRecursionErrorになるN=2×10^5の鎖状木で再帰深さがNに達するiterativeスタックで訪問順を求めpost-order処理する

次のステップ

  • 発展: マッチングの本数も同時に最大化したい場合、状態を(重み,本数)のタプルに拡張する
  • 発展: Edmonds' Blossom Algorithmと比較し木構造がなぜ多項式で解けるかを整理する
  • 発展: 頂点被覆との双対性（Königの定理）との関係を調べる

自己評価

自分の回答

気づき・メモ