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 query " << (i+1) << ": " << solveQuerry(queries[i]) << endl;

    return 0;
}

আউটপুট

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