अवधारणा
किसी दिए गए पेड़ के संबंध में एम नोड्स और प्रत्येक नोड से जुड़ी संख्या के संबंध में, हम किसी भी पेड़ के किनारे को तोड़ सकते हैं जिसके परिणामस्वरूप 2 नए पेड़ बनेंगे। यहां, हमें किनारों की संख्या को इस तरह से गिनना होगा ताकि उस किनारे को तोड़ने के बाद बनाए गए दो पेड़ों में मौजूद बिटवाइज या नोड्स बराबर हों। यह ध्यान दिया जाना चाहिए कि प्रत्येक नोड का मान ≤ 10^6 है।
इनपुट
values[]={1, 3, 1, 3}
1
/ | \
2 3 4 आउटपुट
2
यहां, 1 और 2 के बीच के किनारे को तोड़ा जा सकता है, परिणामी दो पेड़ों का बिटवाइज़ OR 3 होगा।
इसी तरह, 1 और 4 के बीच का किनारा भी तोड़ा जा सकता है।
विधि
यहां, उपर्युक्त समस्या को सरल डीएफएस (डेप्थ फर्स्ट सर्च) को लागू करने से हल किया जा सकता है। क्योंकि नोड्स का मान ≤ 10 ^ 6 है, इसे 22 बाइनरी बिट्स को लागू करने का प्रतिनिधित्व किया जा सकता है। इसके परिणामस्वरूप, बिटवाइज़ या नोड्स के मान का भी 22 बाइनरी बिट्स में प्रतिनिधित्व किया जा सकता है। यहां, विधि यह निर्धारित करने के लिए है कि प्रत्येक बिट को उप-पेड़ के सभी मानों में कितनी बार सेट किया जाता है। प्रत्येक किनारे के लिए हम सत्यापित करेंगे कि 0 से 21 तक प्रत्येक बिट के संबंध में सेट के रूप में उस विशेष बिट के साथ संख्याएं परिणामी पेड़ों में या तो शून्य हैं या दोनों परिणामी पेड़ों में शून्य से अधिक हैं और यदि यह देखा गया है कि स्थिति संतुष्ट है सभी बिट्स के लिए तो उस किनारे को परिणाम में गिना जाता है।
उदाहरण
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
int m1[1000],x1[22];
// Uses array to store the number of times each bit
// is set in all the values of a subtree
int a1[1000][22];
vector<vector<int>> g;
int ans1 = 0;
// Shows function to perform simple DFS
void dfs(int u1, int p1){
for (int i=0;i<g[u1].size();i++) {
int v1 = g[u1][i];
if (v1 != p1) {
dfs(v1, u1);
// Determining the number of times each bit is set
// in all the values of a subtree rooted at v
for (int i = 0; i < 22; i++)
a1[u1][i] += a1[v1][i];
}
}
// Verifying for each bit whether the numbers
// with that particular bit as set are
// either zero in both the resulting trees or
// greater than zero in both the resulting trees
int pp1 = 0;
for (int i = 0; i < 22; i++) {
if (!((a1[u1][i] > 0 && x1[i] - a1[u1][i] > 0)
|| (a1[u1][i] == 0 && x1[i] == 0))) {
pp1 = 1;
break;
}
}
if (pp1 == 0)
ans1++;
}
// Driver code
int main(){
// Number of nodes
int n1 = 4;
// int n1 = 5;
// Uses ArrayList to store the tree
g.resize(n1+1);
// Uses array to store the value of nodes
m1[1] = 1;
m1[2] = 3;
m1[3] = 1;
m1[4] = 3;
/* m1[1] = 2;
m1[2] = 3;
m1[3] = 32;
m1[4] = 43;
m1[5] = 8;*/
//Uses array to store the number of times each bit
// is set in all the values in complete tree
for (int i = 1; i <= n1; i++) {
int y1 = m1[i];
int k1 = 0;
// Determining the set bits in the value of node i
while (y1 != 0) {
int p1 = y1 % 2;
if (p1 == 1) {
x1[k1]++;
a1[i][k1]++;
}
y1 = y1 / 2;
k1++;
}
}
// push_back edges
g[1].push_back(2);
g[2].push_back(1);
g[1].push_back(3);
g[3].push_back(1);
g[1].push_back(4);
g[4].push_back(1);
//g[1].push_back(5);
//g[5].push_back(1);
dfs(1, 0);
cout<<(ans1);
} आउटपुट
2