Khái niệm
Đối với một cây nhất định có m nút và một số liên kết với mọi nút, chúng ta có thể phá vỡ bất kỳ cạnh cây nào sẽ dẫn đến việc hình thành 2 cây mới. Ở đây, chúng ta phải đếm số lượng các cạnh theo cách này sao cho Bitwise OR của các nút có trong hai cây được xây dựng sau khi ngắt cạnh đó bằng nhau. Cần lưu ý rằng giá trị của mỗi nút là ≤ 10 ^ 6.
Đầu vào
values[]={1, 3, 1, 3}
1
/ | \
2 3 4 Đầu ra
2
Ở đây, cạnh giữa 1 và 2 có thể bị phá vỡ, Bitwise OR của hai cây kết quả sẽ là 3.
Theo cách tương tự, cạnh giữa 1 và 4 cũng có thể bị phá vỡ.
Phương pháp
Ở đây, vấn đề nêu trên có thể được giải quyết bằng cách sử dụng DFS (Tìm kiếm đầu tiên theo chiều sâu) đơn giản. Vì giá trị của các nút là ≤ 10 ^ 6, nó có thể được biểu diễn bằng cách thực hiện 22 bit nhị phân. Kết quả là, Bitwise OR của giá trị của các nút cũng có thể được biểu diễn bằng 22 bit nhị phân. Ở đây, phương pháp là xác định số lần mỗi bit được đặt trong tất cả các giá trị của cây asub. Đối với mỗi cạnh, chúng tôi sẽ xác minh rằng đối với mỗi bit từ 0 đến 21, các số có bit cụ thể đó được đặt bằng không trong cả hai cây kết quả hoặc cao hơn 0 trong cả hai cây kết quả và nếu điều kiện được thỏa mãn. đối với tất cả các bit thì cạnh đó được tính trong kết quả.
Ví dụ
// 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);
} Đầu ra
2