একটি ট্রি দেওয়া আছে যেখানে প্রতিটি নোডের একটি ভ্যালু আছে। যেসব এজ ভাঙলে দুইটি সাবট্রি বने এবং তাদের নোড ভ্যালুগুলোর বিটওয়াইজ OR সমান হয়, সেই এজগুলোর সংখ্যা বের করতে হবে। নোড ভ্যালু ≤ 10⁶ (২২ বিট)।
উদাহরণ
values[] = {1, 3, 1, 3}
Tree: 1 connected to 2,3,4
আউটপুট: 2
এজ ১-২ ও ১-৪ ভাঙলে দুই সাবট্রির OR = 3।
অ্যালগরিদম (DFS + বিট কাউন্টিং)
- প্রতিটি বিট (০-২১) এর জন্য পুরো ট্রিতে কতবার সেট আছে তা কাউন্ট করুন (
x[bit])। - DFS দিয়ে প্রতিটি সাবট্রিতে প্রতিটি বিটের ফ্রিকোয়েন্সি কাউন্ট করুন (
a[u][bit])। - এজ u-v (v চাইল্ড) ভাঙলে: সাবট্রি v-তে বিটের কাউন্ট =
a[v][bit], অন্য সাবট্রি-তে =x[bit] - a[v][bit]। - যদি সব বিটের জন্য উভয় পাশে কাউন্ট ০ বা উভয় পাশে >০ হয়, তবে OR সমান। এজ কাউন্ট করুন।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int m[1000], x[22];
int a[1000][22];
vector<vector<int>> g;
int ans = 0;
void dfs(int u, int p) {
for (int v : g[u]) if (v != p) {
dfs(v, u);
for (int i=0;i<22;i++) a[u][i] += a[v][i];
}
bool ok = true;
for (int i=0;i<22;i++) {
if (!((a[u][i]>0 && x[i]-a[u][i]>0) || (a[u][i]==0 && x[i]==0))) {
ok = false; break;
}
}
if (ok) ans++;
}
int main() {
int n = 4;
g.resize(n+1);
m[1]=1; m[2]=3; m[3]=1; m[4]=3;
for (int i=1;i<=n;i++) {
int y=m[i], k=0;
while (y) { if (y%2) { x[k]++; a[i][k]++; } y/=2; k++; }
}
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);
dfs(1, 0);
cout << ans;
return 0;
}
আউটপুট: 2
