इस समस्या में, हमें एक n-ट्री दी गई है और कुछ क्वेरीज हैं जो ट्री के नोड्स हैं। हमारा कार्य दिए गए नोड द्वारा बने सब-ट्री के सभी नोड्स का XOR प्रिंट करना है।
आइए एक उदाहरण से समस्या को समझते हैं,

क्वेरीज - {1, 6, 5}
आउटपुट -
0 0 5
व्याख्या -
1^6^3^2^4^7^5 6^2^4 5
इस समस्या को हल करने के लिए, हम ट्री को एक बार पार करके सब-ट्री के सभी नोड्स का XOR गणना करेंगे और इसे संग्रहीत करेंगे। अब, हम चाइल्ड नोड्स के सब-ट्री के सभी नोड्स का XOR गणना करेंगे और फिर सभी दिए गए सब-ट्री के लिए गणना करेंगे। परिणामों को संग्रहीत करने से समय की बचत होती है।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,
#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 << "Solution for querry " << (i+1) << ": " << solveQuerry(queries[i]) << endl;
return 0;
}
आउटपुट
Solution for querry 1: 0 Solution for querry 2: 2 Solution for querry 3: 5 Solution for querry 4: 7