隣接する2つのノードを同時に選ばない二分木のノード値の最大合計 | C++による動的計画法

はじめに

本記事では、動的計画法(Dynamic Programming)を用いて、「隣接する2つのノードを同時に選ばない」という制約のもとで、二分木のノード値の合計の最大値を求めるアルゴリズムについて解説します。

具体的には、二分木が与えられたとき、親子関係にある(直接つながっている)ノード同士を同時に選ばないという条件を満たすノードの部分集合の中から、ノード値の合計が最大になるものを見つけることが課題です。

アルゴリズムの考え方

木構造上の動的計画法では、各ノードに対して次の2つの状態を定義するのが定石です。

• dp1[node]:そのノード自身を「選ぶ」場合の、その部分木における最大合計
• dp2[node]:そのノード自身を「選ばない」場合の、その部分木における最大合計

これらの値は、葉から根へと向かうDFS(深さ優先探索)によって計算できます。状態遷移は以下の通りです。

• dp1[node] = tree[node] + Σ(すべての子ノード c に対する dp2[c])
  → 自分を選んだ場合は、すべての子ノードを選べない
• dp2[node] = Σ(すべての子ノード c に対する max(dp1[c], dp2[c]))
  → 自分を選ばない場合は、各子ノードについて選ぶ・選ばないの良い方を選べる

最終的な答えは、根ノードにおける max(dp1[根], dp2[根]) となります。

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;
//動的計画法を用いて最大合計を求める
void dfs(int node, int parent, int dp1[], int dp2[], list<int>* adj, int tree[]){
    int sum1 = 0, sum2 = 0;
    for (auto i = adj[node].begin(); i != adj[node].end(); ++i) {
        if (*i == parent)
            continue;
        dfs(*i, node, dp1, dp2, adj, tree);
        sum1 += dp2[*i];
        sum2 += max(dp1[*i], dp2[*i]);
    }
    dp1[node] = tree[node] + sum1;
    dp2[node] = sum2;
}
int main() {
    int n = 5;
    list<int>* adj = new list<int>[n + 1];
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[1].push_back(3);
    adj[3].push_back(1);
    adj[2].push_back(4);
    adj[4].push_back(2);
    adj[2].push_back(5);
    adj[5].push_back(2);
    int tree[n + 1];
    tree[1] = 10;
    tree[2] = 5;
    tree[3] = 11;
    tree[4] = 6;
    tree[5] = 8;
    int dp1[n + 1], dp2[n + 1];
    memset(dp1, 0, sizeof dp1);
    memset(dp2, 0, sizeof dp2);
    dfs(1, 1, dp1, dp2, adj, tree);
    cout << "Maximum sum: " << max(dp1[1], dp2[1]) << endl;
    return 0;
}

出力

Maximum sum: 25

実行例の解説

この例では、木構造は以下のようになっています。

• ノード1(値10)の子:ノード2(値5)、ノード3(値11)
• ノード2(値5)の子:ノード4(値6)、ノード5(値8)

ここで、隣接しないという制約を満たしながら合計を最大化する組み合わせを考えると、ノード3(11)+ ノード4(6)+ ノード5(8)= 25 が最大となります。根であるノード1を選ぶと子のノード2、ノード3が選べなくなるため、あえて根をスキップして孫以下を選ぶ方が合計が大きくなる、という好例です。

計算量

• 時間計算量:O(N) — 各ノードを一度ずつ訪問するだけです。
• 空間計算量:O(N) — 隣接リスト・DPテーブル・再帰スタックにノード数に比例したメモリを使用します。

まとめ

木上のDPでは、「そのノードを選ぶ/選ばない」という2状態を持たせることで、独立集合の最大重みを効率的に求められます。DFSで子の結果を先に計算し、それを根に向かってボトムアップに統合していくのがポイントです。同様のパターンは、木の直径や木DP全般の問題にも応用できるため、ぜひマスターしておきましょう。