C++で木の特定ノードの部分木に含まれる全ノードのXORを求める方法

問題の概要

この問題では、n個のノードからなる木と、木のノードを指定する複数のクエリが与えられます。目的は、指定されたノードを根とする部分木に含まれるすべてのノードの値のXOR(排他的論理和)を求めて出力することです。

具体例を使って問題を理解しましょう。次のような木を考えます。

クエリ: {1, 6, 5}

出力:

0
0
5

計算過程:

1^6^3^2^4^7^5 = 0
6^2^4 = 0
5 = 5

ノード1を根とする部分木は木全体に相当し、そのXORは0になります。同様に、ノード6の部分木(ノード6・2・4)のXORも0、ノード5の部分木はノード5のみなのでXORは5となります。

解法アプローチ

この問題を効率的に解く鍵となるのは前計算(メモ化)の考え方です。手順は以下の通りです。

• 木全体をDFS(深さ優先探索)で一度だけ走査します。
• 各ノードについて、「自分自身の値」と「すべての子ノードの部分木のXOR」を組み合わせた値を計算します。
• 計算結果を配列にキャッシュとして保存します。
• クエリが来たら、保存済みの配列を参照するだけでO(1)で答えを返せます。

クエリごとに木を再走査する必要がないため、全体の計算量は「前計算 O(n)+ 各クエリ O(1)」に抑えられます。結果を保存しておくことが時間短縮のポイントです。

実装例

上記の解法をC++で実装したプログラムが以下です。

#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > graph;
vector<int> values, xorValues;

// 各ノードの部分木のXORを再帰的に計算する
int computeXorValues(int i, int prev){
    int x = values[i];
    for (int j = 0; j < graph[i].size(); j++)
        if (graph[i][j] != prev) {
            x ^= computeXorValues(graph[i][j], i);
        }
    xorValues[i] = x;
    return x;
}

// クエリに対してはキャッシュ済みの値を返すだけ
int solveQuery(int u){
    return xorValues[u];
}

int main(){
    int n = 7;
    graph.resize(n);
    xorValues.resize(n);
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(5);
    graph[2].push_back(6);
    values.push_back(1);
    values.push_back(2);
    values.push_back(3);
    values.push_back(4);
    values.push_back(5);
    values.push_back(6);
    values.push_back(7);
    computeXorValues(0, -1);
    int queries[] = { 0, 2, 4, 6 };
    int q = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < q; i++)
        cout<<"Solution for query "<<(i+1)<<": "<<solveQuery(queries[i])<<endl;
    return 0;
}

出力結果

Solution for query 1: 0
Solution for query 2: 2
Solution for query 3: 5
Solution for query 4: 7

コードの解説

computeXorValues関数: 再帰的に木を走査し、各ノードの部分木のXORを計算します。第2引数のprevは親ノードを表し、親へ逆戻りしないことで無限ループを防いでいます。計算結果はxorValues配列にキャッシュされます。

solveQuery関数: 前計算済みのxorValues配列から該当ノードのXOR値を返すだけのシンプルな関数です。これにより各クエリへの回答が定数時間で完了します。

main関数: 隣接リスト形式でグラフを構築し、各ノードの値を設定した後、根(ノード0)から前計算を実行します。その後、複数のクエリに対して即座に回答を出力します。

まとめ

木構造における部分木のXORクエリ処理は、DFSによる一度の走査と結果のキャッシュで効率的に実現できます。この手法はオイラーツアーやBIT(フェニック木)と組み合わせることで、ノードの値が更新される動的なケースにも拡張可能です。競技プログラミングでも頻出のテクニックなので、ぜひマスターしておきましょう。