Đếm nút cây có trọng số là lũy thừa của 2 trong C++

Cho cây với trọng số nút. Đếm nút có trọng số là lũy thừa của 2 (1, 2, 4, 8, 16...).

Ý tưởng

• DFS trên cây.
• Kiểm tra lũy thừa 2 bằng bitwise: n && !(n & (n - 1)).
• Hàm power_two(node, root) đệ quy đếm.

Ví dụ hoàn chỉnh

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

vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int powers = 0;

void power_two(int node, int root) {
    int set = Node_Weight[node];
    if (set && !(set & (set - 1)))
        powers++;
    for (int it : edge_graph[node]) {
        if (it == root)
            continue;
        power_two(it, node);
    }
}

int main() {
    Node_Weight[2] = 8;
    Node_Weight[1] = 100;
    Node_Weight[4] = 211;
    Node_Weight[3] = 16;
    Node_Weight[8] = 7171;
    Node_Weight[9] = 32;
    edge_graph[2].push_back(1);
    edge_graph[2].push_back(4);
    edge_graph[4].push_back(3);
    edge_graph[4].push_back(8);
    edge_graph[8].push_back(9);
    power_two(2, 2);
    cout << "Số nút có trọng số lũy thừa 2: " << powers;
    return 0;
}

Kết quả

Số nút có trọng số lũy thừa 2: 3