C++ এ প্রদত্ত নোডের সাব-ট্রিতে সমস্ত নোডের XOR

এই সমস্যায়, আমাদের একটি 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