컨셉
m개의 노드와 모든 노드와 관련된 숫자가 있는 주어진 트리와 관련하여 우리는 2개의 새로운 트리가 형성되는 모든 트리 에지를 깰 수 있습니다. 여기에서 우리는 이런 식으로 edge의 수를 세어 그 edge를 깨뜨린 후 생성된 두 트리에 존재하는 노드의 Bitwise OR이 같도록 해야 합니다. 모든 노드의 값은 ≤ 10^6입니다.
입력
values[]={1, 3, 1, 3}
1
/ | \
2 3 4 출력
2
여기에서 1과 2 사이의 가장자리는 깨질 수 있으며, 결과로 나오는 두 트리의 Bitwise OR은 3이 됩니다.
마찬가지로 1과 4 사이의 가장자리도 깨질 수 있습니다.
방법
여기서, 위에서 언급한 문제는 간단한 DFS(Depth First Search)를 구현하면 해결할 수 있다. 노드의 값이 ≤ 10^6이므로 22개의 바이너리 비트를 구현하여 표현할 수 있다. 그 결과 노드 값의 Bitwise OR도 22개의 2진 비트로 표현될 수 있다. 여기서 방법은 서브트리의 모든 값에서 각 비트가 설정되는 횟수를 결정하는 것이다. 각 에지에 대해 0에서 21까지의 각 비트와 관련하여 해당 특정 비트가 설정된 숫자가 결과 트리 모두에서 0이거나 결과 트리 모두에서 0보다 큰지 확인하고 조건이 충족되는 것으로 확인되면 모든 비트에 대해 해당 에지가 결과로 계산됩니다.
예시
// 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