C++で木構造の祖先・子孫関係をクエリで判定する方法

このチュートリアルでは、木構造（ツリー）において、あるノードが別のノードの祖先であるかどうかを効率的に判定するプログラムについて解説します。

具体的には、根付き木とQ個のクエリが与えられます。各クエリで指定された2つのノードのうち、一方がもう一方の祖先であるかどうかを判定するのがタスクです。

アルゴリズムの考え方

この問題は、DFS（深さ優先探索）を利用して各ノードに「入った時刻」と「出た時刻」のタイムスタンプを記録することで、高速に解くことができます。

• timeIn[u]：ノードuに最初に到達した時刻（行きかけ順）
• timeOut[u]：ノードuのすべての子孫の探索を終えて出発する時刻（帰りがけ順）

DFSでは、あるノードの部分木は必ず連続した時間帯に訪問されるという性質（オイラーツアー）があります。これを利用すると、ノードuがノードvの祖先である必要十分条件は次のように表せます。

timeIn[u] ≤ timeIn[v] かつ timeOut[v] ≤ timeOut[u]

つまり、uに入った時刻より後にvに入り、かつvを出るのがuを出る前であれば、vはuの部分木内に存在することになります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// DFSを使ってノード間の関係を調べる
void performingDFS(vector<int> g[], int u, int parent,
int timeIn[], int timeOut[], int& count) {
    timeIn[u] = count++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v != parent)
            performingDFS(g, v, u, timeIn, timeOut, count);
    }
    // ノードに出発時刻を記録
    timeOut[u] = count++;
}
void processingEdges(int edges[][2], int V, int timeIn[], int timeOut[]) {
    vector<int> g[V];
    for (int i = 0; i < V - 1; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int count = 0;
    performingDFS(g, 0, -1, timeIn, timeOut, count);
}
// 祖先関係かどうかを判定する
string whetherAncestor(int u, int v, int timeIn[], int timeOut[]) {
    bool b = (timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u]);
    return (b ? "yes" : "no");
}
int main() {
    int edges[][2] = {
        { 0, 1 },
        { 0, 2 },
        { 1, 3 },
        { 1, 4 },
        { 2, 5 },
    };
    int E = sizeof(edges) / sizeof(edges[0]);
    int V = E + 1;
    int timeIn[V], timeOut[V];
    processingEdges(edges, V, timeIn, timeOut);
    int u = 1;
    int v = 5;
    cout << whetherAncestor(u, v, timeIn, timeOut) << endl;
    return 0;
}

出力結果

no

コードの解説

performingDFS関数

DFSを実行し、ノードに到達した瞬間にtimeInを、その部分木の探索完了時にtimeOutを記録します。親ノードに戻らないようにparent引数で管理している点がポイントです。

processingEdges関数

辺情報をもとに隣接リストを構築し、ルートノード（0番）からDFSを開始します。

whetherAncestor関数

タイムスタンプを比較するだけで祖先関係を判定できます。上記の例では、ノード1とノード5はどちらもルートの子孫ですが互いに親子関係がないため、「no」が出力されます。

計算量

• 前処理（DFS）：O(V)
• クエリ1回あたり：O(1)

前処理を一度行えば、何個のクエリが来ても定数時間で回答できるため、クエリ数が多い場合に特に有効なテクニックです。