XOR của tất cả nút trong cây con của nút cho trước trong C++

Trong bài toán này, cho một cây n-ary và một số truy vấn là các nút của cây. Nhiệm vụ là in ra XOR của tất cả các nút trong cây con được tạo bởi nút cho trước.

Ví dụ:

Truy vấn – {1, 6, 5}

Output –

0 0 5

Giải thích –

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

Để giải, ta tính XOR của tất cả nút trong cây con bằng cách duyệt cây một lần và lưu trữ. Tính XOR của nút con trước, sau đó tính cho các cây con truy vấn. Lưu kết quả giúp tiết kiệm thời gian.

Ví dụ minh họa

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

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

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 solveQuerry(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 << "Kết quả truy vấn " << (i+1) << ": " << solveQuerry(queries[i]) << endl;
    
    return 0;
}

Kết quả

Kết quả truy vấn 1: 0
Kết quả truy vấn 2: 2
Kết quả truy vấn 3: 5
Kết quả truy vấn 4: 7