Query Ancestor-Descendant Relationship ใน Tree ด้วย C++

โจทย์: กำหนด rooted tree และ Q queries แต่ละ query ให้ 2 โหนด ตรวจสอบว่าโหนดหนึ่งเป็น ancestor ของอีกตัวหรือไม่

เทคนิค: DFS Timestamps (Euler Tour)

• DFS จาก root บันทึก timeIn[u] (เวลาเข้า) และ timeOut[u] (เวลาออก)
• u เป็น ancestor ของ v ↔ timeIn[u] ≤ timeIn[v] AND timeOut[v] ≤ timeOut[u]
• ตอบ query O(1) หลัง preprocessing O(N)

ตัวอย่างโค้ด C++

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

void performingDFS(vector<int> g[], int u, int parent, int timeIn[], int timeOut[], int& count) {
    timeIn[u] = count++;
    for (int v : g[u]) {
        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], 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);
    cout << whetherAncestor(1, 5, timeIn, timeOut) << endl; // no
}

อินพุต

edges: (0,1),(0,2),(1,3),(1,4),(2,5), query: u=1, v=5

เอาต์พุท

no

Complexity

• Preprocessing: O(N)
• Per query: O(1)
• Space: O(N)