結果の2つのツリーのビットごとのORがC++で等しくなるように、ツリーで分割できるエッジの数を見つけます

コンセプト

m個のノードとすべてのノードに関連付けられた数を持つ特定のツリーに関して、任意のツリーエッジを壊すことができ、その結果、2つの新しいツリーが形成されます。ここでは、この方法でエッジの数をカウントして、そのエッジを壊した後に構築された2つのツリーに存在するノードのビットごとのORが等しくなるようにする必要があります。すべてのノードの値が≤10^6であることに注意してください。

入力

values[]={1, 3, 1, 3}
     1
   / | \
  2 3 4

出力

2

ここでは、1と2の間のエッジを壊すことができ、結果の2つのツリーのビットごとのORは3になります。

同様に、1と4の間のエッジも壊れる可能性があります。

メソッド

ここで、上記の問題は、単純なDFS（深さ優先探索）を実装することで解決できます。ノードの値は10 ^ 6以下であるため、22個のバイナリビットを実装して表すことができます。この結果、ノードの値のビットごとのORも22のバイナリビットで表すことができます。ここでは、サブツリーのすべての値に各ビットが設定された回数を決定する方法があります。各エッジについて、0から21までの各ビットに関して、その特定のビットが設定された数値が、結果のツリーの両方でゼロであるか、結果の両方のツリーでゼロより大きいこと、および条件が満たされていることが確認されていることを確認します。すべてのビットについて、そのエッジが結果にカウントされます。

例

// 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