C++でツリーノードを削除する：合計値が0の部分木を除去するアルゴリズム

問題概要

根がノード0であるような木構造を考えます。この木には、次の情報が与えられています。

• ノードの総数：nodes
• i番目のノードの値：value[i]
• i番目のノードの親：parent[i]

求めたいのは、「ノードの値の合計が0になる部分木」をすべて削除した後、木に残っているノードの個数です。

たとえば、下図のような木を考えてみましょう。

ノードは全部で7つありますが、出力は2になります。これは、値が0であるノード3を根とする部分木と、ノード2を根とする部分木（4 + (-2) + (-1) + (-1) = 0）が削除対象となり、最終的に残るのがノード0とノード1だけだからです。

解法の考え方

この問題は、深さ優先探索（DFS）を使うことで効率的に解けます。各ノードについて「そのノードを根とする部分木の値の合計」と「部分木に含まれるノード数」を計算し、合計が0であればそのノード数ぶんだけ答えから減算していきます。具体的な手順は以下の通りです。

1. children というマップを作成します。
2. dfs() メソッドを定義します。引数はノード番号、value 配列、隣接リスト形式の graph です。
3. temp をペア (value[node], 1) で初期化します。first は部分木の値の合計、second は部分木のノード数を表します。
4. i を 0 から graph[node] のサイズ未満まで繰り返します。
   • temp2 := dfs(graph[node][i], value, graph) を呼び出します。
   • temp.first に temp2.first を、temp.second に temp2.second をそれぞれ加算します。
5. temp.first が 0 の場合、ans から temp.second を減算し、temp.second を 0 に設定します。
6. temp を返します。
7. メイン側では、nodes、parent 配列、value 配列を受け取ります。
8. n := value 配列の要素数とします。
9. ans := n で初期化します。
10. サイズ n+1 の配列 graph を定義します。
11. i を 1 から n-1 まで繰り返し、graph[parent[i]] に i を挿入して隣接リストを構築します。
12. dfs(0, value, graph) を呼び出します。
13. ans を返します。

C++での実装例

それでは、実際の実装を見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    map <int, int> children;
    int ans;
    pair <int, int> dfs(int node, vector<int>& value, vector <int> graph[]){
        pair <int, int> temp = {value[node], 1};
        for(int i = 0; i < graph[node].size(); i++){
            pair <int, int> temp2 = dfs(graph[node][i], value, graph);
            temp.first += temp2.first;
            temp.second += temp2.second;
        }
        if(temp.first == 0){
            ans -= temp.second;
            temp.second = 0;
        }
        return temp;
    }
    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        int n = value.size();
        ans = n;
        children.clear();
        vector < int > graph[n + 1];
        for(int i = 1; i < n; i++){
            graph[parent[i]].push_back(i);
        }
        dfs(0, value, graph);
        return ans;
    }
};
main(){
    vector<int> v1 = {-1,0,0,1,2,2,2};
    vector<int> v2 = {1,-2,4,0,-2,-1,-1};
    Solution ob;
    cout << (ob.deleteTreeNodes(7,v1, v2));
}

入力

7
[-1,0,0,1,2,2,2]
[1,-2,4,0,-2,-1,-1]

出力

2