ধারণা
m নোড এবং প্রতিটি নোডের সাথে যুক্ত একটি সংখ্যা সহ একটি প্রদত্ত গাছের ক্ষেত্রে, আমরা যে কোনও গাছের প্রান্ত ভেঙে ফেলতে পারি যার ফলে 2টি নতুন গাছ তৈরি হবে। এখানে, আমাদেরকে এইভাবে প্রান্তের সংখ্যা গণনা করতে হবে যাতে সেই প্রান্তটি ভাঙার পরে নির্মিত দুটি গাছে উপস্থিত নোডগুলির বিটওয়াইজ OR সমান হয়। এটি লক্ষ করা উচিত যে প্রতিটি নোডের মান হল ≤ 10^6।
ইনপুট
মান[]={1, 3, 1, 3} 1 / | \ 2 3 4 আউটপুট
2
এখানে, 1 এবং 2-এর মধ্যে প্রান্তটি ভাঙ্গা যেতে পারে, ফলে দুটি গাছের বিটওয়াইজ OR হবে 3।
একইভাবে, 1 এবং 4-এর মধ্যে প্রান্তটিও ভেঙে যেতে পারে।
পদ্ধতি
এখানে, উপরে উল্লিখিত সমস্যাটি সহজ DFS (গভীরতার প্রথম অনুসন্ধান) বাস্তবায়নের মাধ্যমে সমাধান করা যেতে পারে। কারণ নোডের মান ≤ 10^6, এটি 22টি বাইনারি বিট প্রয়োগ করে উপস্থাপন করা যেতে পারে। এর ফলস্বরূপ, নোডের মানের Bitwise OR 22টি বাইনারি বিটেও উপস্থাপন করা যেতে পারে। এখানে, পদ্ধতিটি হল asub-tree-এর সমস্ত মানগুলিতে প্রতিটি বিট কতবার সেট করা হয়েছে তা নির্ধারণ করা। প্রতিটি প্রান্তের জন্য আমরা যাচাই করব যে 0 থেকে 21 পর্যন্ত প্রতিটি বিটের সাপেক্ষে নির্দিষ্ট বিটের সাথে সেট করা সংখ্যাগুলি ফলস্বরূপ উভয় গাছে শূন্য বা উভয় গাছে শূন্যের চেয়ে বেশি এবং যদি দেখা যায় যে শর্তটি সন্তুষ্ট। সমস্ত বিটের জন্য তারপর সেই প্রান্তটি ফলাফলে গণনা করা হয়।
উদাহরণ
নেমস্পেস std;int m1[1000],x1[22];// প্রতিটি বিট// সেট করা কতবার সঞ্চয় করার জন্য অ্যারে ব্যবহার করে একটি সাবট্রিইন্ট a1[1000][22];ভেক্টর<ভেক্টরআউটপুট
2
