Найдите количество ребер, которые можно разбить в дереве, такое, что побитовое ИЛИ полученных двух деревьев равно

Опубликовано: 14 Января, 2022

Дано дерево с n узлами и числом, связанным с каждым узлом. Мы можем сломать любой край дерева, что приведет к образованию 2 новых деревьев. Мы должны подсчитать количество ребер так, чтобы побитовое ИЛИ узлов, присутствующих в двух деревьях, сформированных после разрыва этого ребра, было равным. Значение каждого узла ≤ 10 6 .

Примеры:

Ввод: значения [] = {2, 3, 32, 43, 8}
         1
        / 
       2 3
      / 
     4 5
Выход: 1
Если мы разорвем границу между 2 и 4, то побитовое ИЛИ 
обоих результирующих деревьев будет 43.

Ввод: значения [] = {1, 3, 2, 3}
        1
      / | 
     2 3 4
Выход: 2
Граница между 1 и 2 может быть разорвана, побитовое ИЛИ 
из полученных двух деревьев будет 3.
Точно так же можно сломать край между 1 и 4.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: эту проблему можно решить с помощью простой DFS. Поскольку значение узлов ≤ 10 6 , его можно представить с помощью 22 двоичных разрядов. Побитовое ИЛИ значения узлов также может быть представлено 22 двоичными битами. Подход состоит в том, чтобы узнать, сколько раз каждый бит устанавливался во всех значениях поддерева. Для каждого ребра мы проверим, что для каждого бита от 0 до 21 числа с этим конкретным битом в качестве установленного либо равны нулю в обоих результирующих деревьях, либо больше нуля в обоих результирующих деревьях, и если условие выполняется для всех битов, чем это преимущество засчитывается в результате.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach 
#include<bits/stdc++.h>
using namespace std;
  
    int m[1000],x[22];
      
    // Array to store the number of times each bit 
    // is set in all the values of a subtree 
    int a[1000][22];
      
    vector<vector<int>> g; 
    int ans = 0; 
  
    // Function to perform simple DFS 
    void dfs(int u, int p) 
    { 
        for (int i=0;i<g[u].size();i++) { 
            int v = g[u][i];
            if (v != p) { 
                dfs(v, u); 
  
                // Finding 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++) 
                    a[u][i] += a[v][i]; 
            } 
        } 
  
        // Checking 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 pp = 0; 
        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))) { 
                pp = 1; 
                break; 
            } 
        } 
        if (pp == 0) 
            ans++; 
    } 
  
    // Driver code 
    int main()
    { 
  
        // Number of nodes 
        int n = 4; 
  
        // ArrayList to store the tree 
        g.resize(n+1); 
  
        // Array to store the value of nodes 
        m[1] = 1; 
        m[2] = 3; 
        m[3] = 2; 
        m[4] = 3; 
  
  
        // Array to store the number of times each bit 
        // is set in all the values in complete tree 
          
        for (int i = 1; i <= n; i++) { 
            int y = m[i]; 
            int k = 0; 
  
            // Finding the set bits in the value of node i 
            while (y != 0) { 
                int p = y % 2; 
                if (p == 1) { 
                    x[k]++; 
                    a[i][k]++; 
                } 
                y = y / 2; 
                k++; 
            } 
        } 
  
        // 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); 
        dfs(1, 0); 
        cout<<(ans); 
} 
//contributed by Arnab Kundu

Java

// Java implementation of the approach
import java.util.*;
public class GFG {
    static int m[], a[][], x[];
    static ArrayList<Integer> g[];
    static int ans = 0;
  
    // Function to perform simple DFS
    static void dfs(int u, int p)
    {
        for (int v : g[u]) {
            if (v != p) {
                dfs(v, u);
  
                // Finding 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++)
                    a[u][i] += a[v][i];
            }
        }
  
        // Checking 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 pp = 0;
        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))) {
                pp = 1;
                break;
            }
        }
        if (pp == 0)
            ans++;
    }
  
    // Driver code
    public static void main(String args[])
    {
  
        // Number of nodes
        int n = 4;
  
        // ArrayList to store the tree
        g = new ArrayList[n + 1];
  
        // Array to store the value of nodes
        m = new int[n + 1];
        m[1] = 1;
        m[2] = 3;
        m[3] = 2;
        m[4] = 3;
  
        // Array to store the number of times each bit
        // is set in all the values of a subtree
        a = new int[n + 1][22];
  
        // Array to store the number of times each bit
        // is set in all the values in complete tree
        x = new int[22];
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
            int y = m[i];
            int k = 0;
  
            // Finding the set bits in the value of node i
            while (y != 0) {
                int p = y % 2;
                if (p == 1) {
                    x[k]++;
                    a[i][k]++;
                }
                y = y / 2;
                k++;
            }
        }
  
        // Add edges
        g[1].add(2);
        g[2].add(1);
        g[1].add(3);
        g[3].add(1);
        g[1].add(4);
        g[4].add(1);
        dfs(1, 0);
        System.out.println(ans);
    }
}

Python3

# Python3 implementation of the approach 
m, x = [0] * 1000, [0] * 22
  
# Array to store the number of times each bit 
# is set in all the values of a subtree 
a = [[0 for i in range(22)] 
        for j in range(1000)]
ans = 0
  
# Function to perform simple DFS 
def dfs(u, p):
  
    global ans
    for i in range(0, len(g[u])): 
        v = g[u][i] 
        if v != p: 
            dfs(v, u) 
  
            # Finding the number of times 
            # each bit is set in all the 
            # values of a subtree rooted at v 
            for i in range(0, 22): 
                a[u][i] += a[v][i] 
  
    # Checking 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 
    pp = 0
    for i in range(0, 22): 
        if (not((a[u][i] > 0 and
                 x[i] - a[u][i] > 0) 
            or (a[u][i] == 0 and x[i] == 0))): 
            pp = 1
            break
          
    if pp == 0: 
        ans += 1
  
# Driver code 
if __name__ == "__main__":
  
    # Number of nodes 
    n = 4
  
    # ArrayList to store the tree 
    g = [[] for i in range(n+1)]
  
    # Array to store the value of nodes 
    m[1] = 1
    m[2] = 3
    m[3] = 2
    m[4] = 3
  
    # Array to store the number of times 
    # each bit is set in all the values
    # in complete tree 
    for i in range(1, n+1): 
        y, k = m[i], 0
  
        # Finding the set bits in the 
        # value of node i 
        while y != 0: 
            p = y % 2
            if p == 1: 
                x[k] += 1
                a[i][k] += 1
              
            y = y // 2
            k += 1
          
    # append edges 
    g[1].append(2) 
    g[2].append(1) 
    g[1].append(3) 
    g[3].append(1) 
    g[1].append(4) 
    g[4].append(1) 
    dfs(1, 0) 
    print(ans) 
  
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
  
class GFG 
{
    static int []m;
    static int [,]a;
    static int []x;
    static List<int> []g;
    static int ans = 0;
  
    // Function to perform simple DFS
    static void dfs(int u, int p)
    {
        foreach (int v in g[u])
        {
            if (v != p) 
            {
                dfs(v, u);
  
                // Finding 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++)
                    a[u,i] += a[v,i];
            }
        }
  
        // Checking 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 pp = 0;
        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)))
            {
                pp = 1;
                break;
            }
        }
        if (pp == 0
Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023