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