Java | Tree Dynamic Programming

Java Java
スポンサーリンク

Javaで学ぶ「木DP（Tree Dynamic Programming）」（後半）

前半では、 「動的計画法とは何か」 「木構造とは何か」 「木DPとは、各ノードを根とする部分木に対して値を定義し、子の値を使って親の値を計算すること」 を、部分木の合計値というシンプルな例で整理しました。

後半では、そこから一歩進んで、 別の木DPの具体例（高さ・最大値・条件付きカウント）、 根から見たDPと子から見たDPの違い、 計算量やスタックの深さ、セキュリティの観点からの注意点、 そして木DPが実際に役立つ場面のイメージまで、 初心者向けにかみ砕いて深掘りしていきます。

例題1：部分木の高さを木DPで求める

まず、「部分木の高さ」を求める木DPを考えてみます。 ここでいう高さとは、「そのノードから一番深い葉までの距離」です。 葉は「子を持たないノード」です。

例えば、次のような木を考えます。

根が 5 その子が 3 と 7 3 の子が 2

このとき、 葉は 2 と 7 です。 高さは、 ノード 2 の高さが 0（自分自身が葉） ノード 3 の高さが 1（3 → 2） ノード 7 の高さが 0 根 5 の高さが 2（5 → 3 → 2） となります。

この「高さ」を木DPで求めるには、 各ノードに対して「そのノードを根とする部分木の高さ」を定義し、 子の高さを使って親の高さを計算します。

Javaコードで書くと、次のようになります。

class Node {
    int value;
    List<Node> children = new ArrayList<>();
    int height; // 部分木の高さを保存するフィールド

    Node(int value) {
        this.value = value;
    }

    void addChild(Node child) {
        children.add(child);
    }
}

public class TreeHeightDP {

    public static int computeHeight(Node node) {
        if (node.children.isEmpty()) {
            node.height = 0;
            return 0;
        }

        int maxChildHeight = 0;
        for (Node child : node.children) {
            int h = computeHeight(child);
            if (h > maxChildHeight) {
                maxChildHeight = h;
            }
        }

        node.height = maxChildHeight + 1;
        return node.height;
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        Node child1 = new Node(3);
        Node child2 = new Node(7);
        root.addChild(child1);
        root.addChild(child2);

        Node grandChild = new Node(2);
        child1.addChild(grandChild);

        computeHeight(root);

        System.out.println("root height: " + root.height);         // 2
        System.out.println("child1 height: " + child1.height);     // 1
        System.out.println("child2 height: " + child2.height);     // 0
        System.out.println("grandChild height: " + grandChild.height); // 0
    }
}
Java

このコードの重要なポイントは、 葉ノードの高さを 0 とし、 親ノードの高さを「子の高さの最大値 + 1」としていることです。

つまり、 部分問題は「あるノードを根とする部分木の高さ」であり、 その答えは「子の部分木の高さ」を使って計算されています。

これが、木DPの典型的なパターンです。 「子の答えを集めて、親の答えを作る」という構造が、 高さという別の値でもそのまま使われています。

例題2：部分木の最大値を木DPで求める

次に、「部分木の最大値」を求める木DPを考えてみます。 各ノードに整数 value が入っている木があり、 そのノードを根とする部分木の中で最大の value を知りたい、 という問題です。

このときも、 各ノードに対して「その部分木の最大値」を定義し、 子の最大値を使って親の最大値を計算します。

Javaコードで書くと、次のようになります。

class NodeMax {
    int value;
    List<NodeMax> children = new ArrayList<>();
    int maxInSubtree;

    NodeMax(int value) {
        this.value = value;
    }

    void addChild(NodeMax child) {
        children.add(child);
    }
}

public class TreeMaxDP {

    public static int computeMax(NodeMax node) {
        int max = node.value;

        for (NodeMax child : node.children) {
            int childMax = computeMax(child);
            if (childMax > max) {
                max = childMax;
            }
        }

        node.maxInSubtree = max;
        return max;
    }

    public static void main(String[] args) {
        NodeMax root = new NodeMax(5);
        NodeMax child1 = new NodeMax(3);
        NodeMax child2 = new NodeMax(7);
        root.addChild(child1);
        root.addChild(child2);

        NodeMax grandChild = new NodeMax(10);
        child1.addChild(grandChild);

        computeMax(root);

        System.out.println("root max: " + root.maxInSubtree);         // 10
        System.out.println("child1 max: " + child1.maxInSubtree);     // 10
        System.out.println("child2 max: " + child2.maxInSubtree);     // 7
        System.out.println("grandChild max: " + grandChild.maxInSubtree); // 10
    }
}
Java

ここでも、 部分問題は「あるノードを根とする部分木の最大値」であり、 その答えは「子の部分木の最大値」を使って計算されています。

このように、 合計値、高さ、最大値といったさまざまな値を 「部分木ごとに定義し、子の値を使って親の値を計算する」 というパターンで扱えることが、木DPの強さです。

例題3：条件付きカウントを木DPで行う

もう一つ、少しだけ応用的な例として 「部分木の中で、ある条件を満たすノードの数を数える」 木DPを考えてみます。

例えば、 「value が 5 以上のノードの数を、各部分木ごとに数えたい」 という問題です。

このとき、 各ノードに対して「その部分木の中で value が 5 以上のノード数」を定義し、 子のカウントを使って親のカウントを計算します。

Javaコードで書くと、次のようになります。

class NodeCount {
    int value;
    List<NodeCount> children = new ArrayList<>();
    int countGE5;

    NodeCount(int value) {
        this.value = value;
    }

    void addChild(NodeCount child) {
        children.add(child);
    }
}

public class TreeCountDP {

    public static int computeCount(NodeCount node) {
        int count = (node.value >= 5) ? 1 : 0;

        for (NodeCount child : node.children) {
            count += computeCount(child);
        }

        node.countGE5 = count;
        return count;
    }

    public static void main(String[] args) {
        NodeCount root = new NodeCount(5);
        NodeCount child1 = new NodeCount(3);
        NodeCount child2 = new NodeCount(7);
        root.addChild(child1);
        root.addChild(child2);

        NodeCount grandChild = new NodeCount(9);
        child1.addChild(grandChild);

        computeCount(root);

        System.out.println("root countGE5: " + root.countGE5);         // 3 (5, 7, 9)
        System.out.println("child1 countGE5: " + child1.countGE5);     // 1 (9)
        System.out.println("child2 countGE5: " + child2.countGE5);     // 1 (7)
        System.out.println("grandChild countGE5: " + grandChild.countGE5); // 1 (9)
    }
}
Java

ここでも、 部分問題は「あるノードを根とする部分木の中で条件を満たすノード数」であり、 その答えは「子の部分木のカウント」を使って計算されています。

このように、 木DPは「部分木に関するあらゆる集計」を 再帰的に、かつ効率よく行うための枠組みだと捉えることができます。

根から見たDPと「再根付き」DPの違い

ここまでの例は、 「ある根からスタートして、下に向かって部分木の値を計算する」 という形でした。

競技プログラミングなどでは、 「どのノードを根とした場合でも、その部分木の値を知りたい」 というような問題が登場します。

例えば、 「木のどのノードを根にしても、その部分木の合計値を知りたい」 といった問題です。

このときに登場するのが「再根付き（rerooting）DP」です。

再根付きDPでは、 まず一つの根から見た木DPを行い、 その結果を使って「根を別のノードに移したときの値」を 効率よく計算します。

これは少し高度なテーマなので、 ここでは直感だけを共有しておきます。

一つの根から見たときの部分木の値を「下向きの情報」として持ち、 親から子へ「上向きの情報」を伝えることで、 どのノードを根にしても必要な値が計算できる、 という構造になっています。

木DPに慣れてきた読者は、 この「再根付きDP」に挑戦してみると、 木DPの世界が一気に広がります。

計算量・スタックの深さ・セキュリティの観点から見た木DP

木DPは非常に強力ですが、 実務やセキュリティの観点ではいくつか注意点があります。

まず、計算量です。 木DPは、基本的に「各ノードを一度ずつ訪れる」ため、 ノード数を N とすると O(N) で動きます。 これは非常に効率的で、 大きな木に対しても現実的な時間で処理できます。

しかし、再帰を使うため、 スタックの深さに注意が必要です。 木が「一本の鎖」のように深くなっている場合、 再帰の深さが N になり、 N が大きいと StackOverflowError を引き起こす可能性があります。

セキュリティの観点では、 外部入力から渡された木構造に対して 無制限に再帰木DPを行うと、 攻撃者が「極端に深い木」を送ることで スタックを枯渇させる可能性があります。

安全な設計としては、 木の深さに上限を設ける、 再帰ではなく自前のスタックを使った非再帰実装にする、 異常な構造（極端に深い一本鎖など）を事前に検証して拒否する、 といった対策が重要になります。

木DPは「部分問題を使い回す」という意味で効率的ですが、 「どこまで再帰を許すか」という視点を持たないと セキュリティリスクにもなり得ます。

木DPが役立つ具体的な場面のイメージ

木DPは、競技プログラミングだけの技術ではありません。 実務でも、階層構造を扱う場面でそのまま役立ちます。

例えば、 フォルダ階層のサイズ集計 組織図の人数集計や最大階層の計算 メニュー構造の表示制御（条件付きで表示するノード数の計算） 権限の伝播の解析（ある権限がどのノードまで届くかの集計）

こうした場面で、 「各ノードを根とする部分木に対して値を定義し、 子の値を使って親の値を計算する」 という木DPの発想は、そのまま使えます。

木DPを理解すると、 階層構造を扱う問題に対して 「どうやって効率よく集計するか」を 自分の頭で設計できるようになります。

それは、単なるアルゴリズムのテクニックではなく、 システム全体を見渡す設計力につながっていきます。

後半のまとめ

後半では、木DPを一段深く理解するために

部分木の高さを求める木DP 部分木の最大値を求める木DP 条件付きカウント（value が 5 以上のノード数）を行う木DP 「各ノードを根とする部分木に対して値を定義し、子の値を使って親の値を計算する」という基本パターンの再確認 根から見たDPと「再根付き」DPの直感 計算量・スタックの深さ・セキュリティの観点から見た木DPの注意点 実務で木DPが役立つ具体的な場面のイメージ

を整理しました。

木DPは、「木構造」と「動的計画法」という二つの強力な考え方が合わさったテクニックです。 この組み合わせを自分のものにできると、 階層構造を扱うあらゆる問題に対して、 一段深いレベルでアルゴリズムを設計できるようになります。

前へ
12
スポンサーリンク
タイトルとURLをコピーしました