C++でn分木の偶数サイズの部分木を数える方法

問題の概要

この問題では、n分木(n-ary tree)の構造を表す隣接リストが与えられ、その木に含まれる偶数サイズの部分木の個数を求めることが課題となります。

n分木とは、一般的に次のような階層構造で表現されるノードの集合として定義されます。

• 木はルートノードから始まる。
• 各ノードは、子ノードへのポインタのリストを保持する。
• 各ノードが持てる子ノードの数はm以下である。

具体例で問題を理解する

入力:

ノード7を根とする木(7の子は2と9、2の子は0と1、9の子は3、3の子は8、0の子は5)

出力: 4

説明:

• ノード7を根とする部分木のサイズは8(偶数)→ カウント
• ノード2を根とする部分木のサイズは4(偶数)→ カウント
• ノード0を根とする部分木のサイズは2(偶数)→ カウント
• ノード3を根とする部分木のサイズは2(偶数)→ カウント

したがって、偶数サイズの部分木は合計4個存在します。

解法のアプローチ

最もシンプルな方法は、各ノードについて「そのノードを根とする部分木のサイズ」を数え、サイズが偶数であればカウンタ(evenTreeCount)を1増やすというものです。この処理にはDFS(深さ優先探索)を利用します。

この問題は木を1回走査するだけで解くことができます。各子ノードの部分木サイズを再帰的に求め、その合計(自分自身を含む)が偶数であればカウンタを増やし、奇数であればそのまま親ノードへ返します。

アルゴリズムの手順

1. ルートノードからDFSを開始する。
2. 各ノードのサイズを1(自分自身)で初期化する。
3. すべての子ノードに対して再帰的にDFSを呼び出し、返されたサイズを加算する。
4. 計算されたサイズが偶数であればカウンタを1増やす。
5. サイズを親ノードに返す。

各ノードを1度だけ訪問するため、時間計算量はO(n)と非常に効率的です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

int countEvenSizeSubTree(vector<int> adj[], int n, int v, int& evenCount) {
    int size = 1;
    for (auto ele : adj[v]) {
        size += countEvenSizeSubTree(adj, n, ele, evenCount);
    }
    if (size % 2 == 0)
        evenCount++;
    return size;
}

int main() {
    int n;
    n = 10;

    vector<int> adj[n + 1];
    adj[7].push_back(2);
    adj[7].push_back(9);
    adj[2].push_back(0);
    adj[2].push_back(1);
    adj[9].push_back(3);
    adj[3].push_back(8);
    adj[0].push_back(5);

    int evenCount = 0;
    countEvenSizeSubTree(adj, n, 7, evenCount);
    cout << "偶数サイズの部分木の数: " << evenCount;
    return 0;
}

出力

偶数サイズの部分木の数: 4

まとめ

n分木の偶数サイズの部分木を数える問題は、DFSを用いて各ノードの部分木サイズを再帰的に計算することで、木を1回走査するだけで効率的に解くことができます。サイズが偶数になるたびにカウンタを増やすだけでよく、実装も非常にシンプルです。