अवधारणा
दिए गए m नोड्स वाले ट्री और हर नोड से जुड़ी एक संख्या के संबंध में, हम किसी भी ट्री किनारे को तोड़ सकते हैं जिसके परिणामस्वरूप 2 नए ट्री बनेंगे। यहां, हमें उन किनारों की संख्या गिननी है ताकि उस किनारे को तोड़ने के बाद बने दो ट्री में मौजूद नोड्स का बिटवाइज OR बराबर हो। ध्यान दिया जाना चाहिए कि हर नोड का मान ≤ 10^6 है।
इनपुट
values[]={1, 3, 1, 3} 1 / | \ 2 3 4
आउटपुट
2
यहां, 1 और 2 के बीच का किनारा तोड़ा जा सकता है, परिणामी दो ट्री का बिटवाइज OR 3 होगा।
इसी तरह, 1 और 4 के बीच का किनारा भी तोड़ा जा सकता है।
विधि
उपरोक्त समस्या को सरल DFS (डेप्थ फर्स्ट सर्च) का उपयोग करके हल किया जा सकता है। क्योंकि नोड्स का मान ≤ 10^6 है, इसे 22 बाइनरी बिट्स का उपयोग करके दर्शाया जा सकता है। परिणामस्वरूप, नोड्स के मान का बिटवाइज OR भी 22 बाइनरी बिट्स में दर्शाया जा सकता है। यहां, विधि एक उप-ट्री में सभी मानों में प्रत्येक बिट के सेट होने की संख्या निर्धारित करना है। प्रत्येक किनारे के लिए हम जांचेंगे कि 0 से 21 तक प्रत्येक बिट के लिए उस विशेष बिट के सेट होने वाली संख्या दोनों परिणामी ट्री में या तो शून्य है या दोनों में शून्य से अधिक है और यदि देखा जाता है कि सभी बिट्स के लिए शर्त पूरी होती है तो उस किनारे को परिणाम में गिना जाता है।
उदाहरण
// दृष्टिकोण का C++ कार्यान्वयन #include<bits/stdc++.h> using namespace std; int m1[1000],x1[22]; // प्रत्येक बिट के सेट होने की संख्या संग्रहीत करने के लिए सरणी // एक उप-ट्री के सभी मानों में int a1[1000][22]; vector<vector<int>> g; int ans1 = 0; // सरल 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); // उप-ट्री में सभी मानों में प्रत्येक बिट के सेट होने की संख्या निर्धारित करना // v पर आधारित for (int i = 0; i < 22; i++) a1[u1][i] += a1[v1][i]; } } // प्रत्येक बिट के लिए जांचना कि क्या उस विशेष बिट के सेट होने वाली संख्या // दोनों परिणामी ट्री में या तो शून्य है या दोनों में शून्य से अधिक है 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++; } // ड्राइवर कोड int main(){ // नोड्स की संख्या int n1 = 4; // int n1 = 5; // ट्री संग्रहीत करने के लिए ArrayList का उपयोग g.resize(n1+1); // नोड्स के मान संग्रहीत करने के लिए सरणी 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;*/ // पूर्ण ट्री में सभी मानों में प्रत्येक बिट के सेट होने की संख्या संग्रहीत करने के लिए सरणी for (int i = 1; i <= n1; i++) { int y1 = m1[i]; int k1 = 0; // नोड i के मान में सेट बिट्स निर्धारित करना while (y1 != 0) { int p1 = y1 % 2; if (p1 == 1) { x1[k1]++; a1[i][k1]++; } y1 = y1 / 2; k1++; } } // एज जोड़ें 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
