XOR ของโหนดทั้งหมดใน subtree ของโหนดที่กำหนด (C++)

โจทย์

ได้รับต้นไม้ (tree) n โหนด และ queries เป็นโหนดต่างๆ ต้องการหา XOR ของโหนดทั้งหมดใน subtree ที่รากอยู่ที่โหนดที่ query

ตัวอย่าง

Queries: {1, 6, 5}
Output: 0, 0, 5

คำอธิบาย

Query 1 (node 1): 1^6^3^2^4^7^5 = 0
Query 2 (node 6): 6^2^4 = 0  
Query 3 (node 5): 5 = 5

วิธีแก้ปัญหา

1. ทำ DFS (Depth First Search) จากรากต้นไม้ คำนวณ XOR ของ subtree ทุกโหนด
2. เก็บผลลัพธ์ไว้ใน array xorValues[]
3. ตอบ query แต่ละอันใน O(1) โดยดูค่าใน xorValues[u]

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

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

vector<vector<int>> graph;
vector<int> values, xorValues;

int computeXorValues(int u, int parent) {
    int x = values[u];
    for (int v : graph[u]) {
        if (v != parent) {
            x ^= computeXorValues(v, u);
        }
    }
    xorValues[u] = x;
    return x;
}

int solveQuery(int u) {
    return xorValues[u];
}

int main() {
    int n = 7;
    graph.resize(n);
    xorValues.resize(n);
    
    // สร้างต้นไม้ (0-indexed)
    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 = {1, 2, 3, 4, 5, 6, 7};
    
    // คำนวณ XOR ของทุก subtree
    computeXorValues(0, -1);
    
    int queries[] = {0, 2, 4, 6};  // 0-indexed
    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

Complexity

• Preprocessing: O(N) - DFS ครั้งเดียว
• Query: O(1) - table lookup
• Space: O(N) - เก็บ graph, values, xorValues

การประยุกต์ใช้

เทคนิคนี้เรียกว่า Subtree Query with DFS ใช้ได้กับ operation อื่นๆ ที่เป็น associative และ commutative เช่น Sum, Min, Max, GCD โดยแค่เปลี่ยน operator จาก XOR เป็น operation ที่ต้องการ

สรุป

การ precompute XOR ของทุก subtree ด้วย DFS ครั้งเดียว แล้วตอบ query ใน O(1) เป็นวิธีมาตรฐานสำหรับ subtree query problems เหมาะสำหรับโจทย์ที่มี queries หลายๆ ตัว