Tìm số cạnh có thể gãy trong cây sao cho OR bitwise của hai cây con bằng nhau trong C++

Khái niệm

Cho cây m nút, mỗi nút có giá trị. Gãy một cạnh tạo ra 2 cây mới. Đếm số cạnh gãy sao cho OR bitwise của các nút trong hai cây kết quả bằng nhau. Giá trị nút ≤ 10^6.

Ví dụ

Đầu vào: values[] = {1, 3, 1, 3}, cây: 1 kết nối 2,3,4

Đầu ra: 2

Gãy cạnh 1-2: OR cả hai cây = 3. Gãy cạnh 1-4: OR cả hai cây = 3.

Phương pháp

Dùng DFS đơn giản. Giá trị nút ≤ 10^6 → 22 bit nhị phân. OR bitwise cũng dùng 22 bit. Đếm số lần mỗi bit được set trong giá trị các nút của cây con. Với mỗi cạnh, kiểm tra từng bit 0-21: số nút có bit set phải là 0 ở cả hai cây hoặc >0 ở cả hai. Nếu thỏa mãn cho tất cả bit, đếm cạnh đó.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int m1[1000], x1[22];
int a1[1000][22];
vector<vector<int>> g;
int ans1 = 0;

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);
            for (int i = 0; i < 22; i++)
                a1[u1][i] += a1[v1][i];
        }
    }
    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++;
}

int main() {
    int n1 = 4;
    g.resize(n1 + 1);
    m1[1] = 1; m1[2] = 3; m1[3] = 1; m1[4] = 3;
    for (int i = 1; i <= n1; i++) {
        int y1 = m1[i], k1 = 0;
        while (y1 != 0) {
            int p1 = y1 % 2;
            if (p1 == 1) { x1[k1]++; a1[i][k1]++; }
            y1 /= 2; k1++;
        }
    }
    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 << ans1;
}