木 DP (ABC Tree DP)
Table of Contents
🌳 木DP 問題集
AtCoder と AOJ から、木DPを体系的に学べる問題を難易度順にまとめました。
🌱 初級
1. ABC036 D - 塗り絵
💡 ヒント
テーマ：最大独立集合 / 0-1 木DP
頂点 $v$ について
- $dp[v][0]$ : vを選ばない
- $dp[v][1]$ : vを選ぶ
状態遷移：
$dp[v][0] = \prod_{u \in child(v)} (dp[u][0] + dp[u][1])$
$dp[v][1] = \prod_{u \in child(v)} dp[u][0]$
DFSで子から順に計算する。
2. ABC138 D - Ki
💡 ヒント
テーマ：木上の累積和
根からDFSを行い、
value[child] += value[parent]
と親から子へ値を伝播させる。
3. AOJ GRL_5_A - Diameter of a Tree
💡 ヒント
テーマ：木の直径
- 任意の頂点から最遠点 $u$ を求める
- $u$ から最遠点を求める
これが直径になる。
木DPというより2回DFS。
💡 解説
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
using P = pair<ll, ll>;
vector<vector<P>> to(N);
rep(i, N - 1) {
ll s, t, w;
cin >> s >> t >> w;
to[s].pb({t, w});
to[t].pb({s, w});
}
ll ans = 0;
auto dfs = [&](auto dfs, int now, int p, ll sum) -> ll {
ll mx = 0;
for (auto [nx, w] : to[now]) {
if (nx == p) continue;
ll r = dfs(dfs, nx, now, w);
chmax(ans, mx + r);
chmax(mx, r);
}
return sum + mx;
};
dfs(dfs, 0, -1, 0);
cout << ans << endl;
}
🌿 初中級
4. ABC160 F - Distributing Integers
💡 ヒント
テーマ：re-rooting DP（全方位木DP）
- まず根を固定して部分木DPを計算
- 親から子へ値を渡す
親方向からの寄与を持たせるのが本質。
5. ABC220 F - Distance Sums 2
💡 ヒント
テーマ：全頂点からの距離和 / re-rooting
部分木サイズを $sz[v]$ とすると、
$ans[child] = ans[parent] - sz[child] + (N - sz[child])$
- まず1頂点を根として距離和を求める
- 上式で re-root する
部分木サイズを事前に計算しておく。
🌲 中級
6. ARC112 C - DFS Game
💡 ヒント
テーマ：部分木マージDP
子のDPを順番にマージする。
小さいDPからマージすると高速化できる場合もある（small-to-large）。
7. ABC222 F - Expensive Expense
💡 ヒント
テーマ：重み付き木 + re-rooting
- 各頂点からの「部分木内最遠距離」を管理
- 親側からの最大値も持つ
「内側最大」と「外側最大」を分けて考える。
🌳 上級
8. AGC009 C - Division into Two
💡 ヒント
テーマ：木DP + 数え上げ
制約を整理し、部分木ごとに組み合わせを数える。
mod計算と場合分けが多い。
🎯 木DPパターン整理
💡 代表的なパターン
① 足し上げ型
$dp[v] = \sum_{u \in child(v)} dp[u]$
② 0/1 型
頂点を選ぶ / 選ばない
③ マージ型
部分木DPを順番に統合する。
④ re-rooting 型
$ans[child] = ans[parent] + \Delta$
親から子へ値を渡すのが本質。
🚀 学習順おすすめ
- ABC036 D
- ABC160 F
- ABC220 F
- ARC112 C
- AGC系