XOR của tất cả các nút trong cây con của nút đã cho trong C ++

Trong bài toán này, chúng ta được đưa ra một cây n và có một số truy vấn là các nút của cây. Nhiệm vụ của chúng ta là in XOR của tất cả các nút của cây con được tạo bởi nút đã cho.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Đầu ra -

0
0
5

Giải thích -

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

Để giải quyết vấn đề này, chúng ta sẽ tính xor của tất cả các nút của cây con bằng cách duyệt qua cây một lần và lưu trữ nó. Bây giờ, chúng ta sẽ tính xor của tất cả các nút của cây con nếu các nút con và sau đó tính toán cho tất cả các cây con đã cho. Lưu trữ kết quả giúp tiết kiệm thời gian.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

Solution for querry 1: 0
Solution for querry 2: 2
Solution for querry 3: 5
Solution for querry 4: 7