二分リンゴの木 (Binary Apple Tree)

この問題は「樹上ナップサック」の典型例です。木の枝に重みが付いており、保持する枝の数を制限したときの最大価値を求めます。

状態定義:
dp[u][j] : 頂点 u を根とする部分木において、j 本の枝を残したときの最大価値。

遷移式:
dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + edge_weight)
ここで v は u の子、k は子 v の部分木で選択する枝の数です。+1 は u-v を結ぶ枝を考慮しています。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int to, weight;
};

vector<Edge> adj[105];
int dp[105][105];
int subtree_size[105];
int N, Q;

void compute_dp(int u, int p) {
    for (auto& edge : adj[u]) {
        int v = edge.to;
        if (v == p) continue;
        compute_dp(v, u);
        subtree_size[u] += subtree_size[v] + 1;
        for (int j = min(Q, subtree_size[u]); j >= 1; --j) {
            for (int k = 0; k <= min(j - 1, subtree_size[v]); ++k) {
                dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + edge.weight);
            }
        }
    }
}

int main() {
    cin >> N >> Q;
    for (int i = 0; i < N - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    compute_dp(1, 0);
    cout << dp[1][Q] << endl;
    return 0;
}

選科 (Course Selection)

依存関係のある科目の選択問題です。仮想的な根（頂点0）を追加することで、森を1つの木として扱います。

状態定義:
dp[u][j] : 頂点 u の部分木から j 個の科目を選択したときの最大スコア。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> children[305];
int scores[305];
int f[305][305];
int n, m;

void solve(int u) {
    f[u][1] = scores[u];
    for (int v : children[u]) {
        solve(v);
        for (int j = m + 1; j >= 1; --j) {
            for (int k = 0; k < j; ++k) {
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int parent, s;
        cin >> parent >> s;
        scores[i] = s;
        children[parent].push_back(i);
    }
    solve(0);
    cout << f[0][m + 1] << endl;
    return 0;
}

数字変換 (Number Conversion)

約数の和に基づく数値変換の連鎖を木と見なし、その木の直径を求める問題です。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 50005;
int sum_div[MAXN], head[MAXN], edge_cnt;
int max_len, target_node;

struct Edge {
    int to, next;
} e[MAXN * 2];

void add_edge(int u, int v) {
    e[++edge_cnt] = {v, head[u]};
    head[u] = edge_cnt;
}

void find_diameter(int u, int p, int depth) {
    if (depth > max_len) {
        max_len = depth;
        target_node = u;
    }
    for (int i = head[u]; i; i = e[i].next) {
        if (e[i].to != p) find_diameter(e[i].to, u, depth + 1);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 2 * i; j <= n; j += i) sum_div[j] += i;
    }
    for (int i = 1; i <= n; ++i) {
        if (sum_div[i] < i && sum_div[i] != 0) {
            add_edge(i, sum_div[i]);
            add_edge(sum_div[i], i);
        }
    }
    find_diameter(1, 0, 0);
    max_len = 0;
    find_diameter(target_node, 0, 0);
    cout << max_len << endl;
    return 0;
}

戦略ゲーム (Strategic Game)

最小点カバー問題の木バージョンです。各ノードに兵士を置くか置かないかで状態を分けます。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[1505][2];
vector<int> g[1505];

void dfs(int u, int p) {
    dp[u][0] = 0;
    dp[u][1] = 1;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; ++i) g[i].clear();
        for (int i = 0; i < n; ++i) {
            int u, k, v;
            scanf("%d:(%d)", &u, &k);
            while (k--) {
                cin >> v;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        dfs(0, -1);
        cout << min(dp[0][0], dp[0][1]) << endl;
    }
    return 0;
}

皇宮看守 (Palace Guard)

各ノードが「自分自身で守る」「親に守られる」「子に守られる」のいずれかの状態を持つ木DPです。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;
int cost[1505], dp[1505][3];
vector<int> tree[1505];

void tree_dp(int u, int p) {
    int sum_min_01 = 0;
    bool has_guard_child = false;
    int min_diff = INF;

    dp[u][1] = cost[u];
    dp[u][0] = 0;
    dp[u][2] = 0;

    for (int v : tree[u]) {
        if (v == p) continue;
        tree_dp(v, u);
        
        dp[u][1] += min({dp[v][0], dp[v][1], dp[v][2]});
        dp[u][2] += min(dp[v][0], dp[v][1]);
        
        if (dp[v][1] <= dp[v][0]) {
            has_guard_child = true;
            sum_min_01 += dp[v][1];
        } else {
            sum_min_01 += dp[v][0];
            min_diff = min(min_diff, dp[v][1] - dp[v][0]);
        }
    }
    dp[u][0] = has_guard_child ? sum_min_01 : sum_min_01 + min_diff;
}

加分二分探索木 (Bonus Binary Tree)

中順走査が与えられたときの最大スコアを持つ二分木を構成する区間DPに近い樹形DPです。

#include <iostream>
#include <algorithm>

using namespace std;

long long dp[55][55];
int root[55][55];
int val[55];

void print_preorder(int l, int r) {
    if (l > r) return;
    cout << root[l][r] << " ";
    print_preorder(l, root[l][r] - 1);
    print_preorder(root[l][r] + 1, r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 1; i <= n + 1; ++i) {
        for (int j = 0; j <= n; ++j) dp[i][j] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = val[i];
        root[i][i] = i;
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            for (int k = i; k <= j; ++k) {
                long long score = dp[i][k - 1] * dp[k + 1][j] + val[k];
                if (score > dp[i][j]) {
                    dp[i][j] = score;
                    root[i][j] = k;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    print_preorder(1, n);
    return 0;
}

騎士 (Knight)

基環樹（1つのサイクルを含む連結グラフ）上での最大独立集合問題です。サイクル内の1辺を切り離し、その端点を使用する場合としない場合で通常の樹形DPを行います。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const int MAXN = 1000005;
vector<int> g[MAXN];
ll val[MAXN], f[MAXN][2];
int parent[MAXN], vis[MAXN];
int root1, root2, edge_idx;

void dfs_find_cycle(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (v == parent[u]) continue;
        if (vis[v]) {
            root1 = u;
            root2 = v;
            edge_idx = v; 
            continue;
        }
        parent[v] = u;
        dfs_find_cycle(v);
    }
}

void dp_tree(int u, int avoid) {
    f[u][0] = 0;
    f[u][1] = val[u];
    for (int v : g[u]) {
        if (v == avoid || v == parent[u]) continue;
        dp_tree(v, avoid);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int v;
        scanf("%lld %d", &val[i], &v);
        g[v].push_back(i);
        g[i].push_back(v);
    }
    // グラフが複数の連結成分（基環樹）から成る場合を考慮してループ
    // 実装の詳細は省略
    return 0;
}