Đếm nút cây có tổng chữ số trọng số là số lẻ trong C++

Cho cây với trọng số nút. Đếm nút mà tổng các chữ số của trọng số là số lẻ.

Ý tưởng

• DFS trên cây.
• Hàm sum_total(n) tính tổng chữ số: lặp n % 10 cộng dồn, n /= 10.
• Hàm odd_weight(node, root) đệ quy đếm nếu tổng chữ số lẻ.

Ví dụ hoàn chỉnh

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

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

int sum_total(int check) {
    int total = 0;
    while (check) {
        total += check % 10;
        check = check / 10;
    }
    return total;
}

void odd_weight(int node, int root) {
    int total = sum_total(Node_Weight[node]);
    if (total % 2 == 1)
        sum++;
    for (int it : edge_graph[node]) {
        if (it == root)
            continue;
        odd_weight(it, node);
    }
}

int main() {
    Node_Weight[2] = 23;
    Node_Weight[1] = 141;
    Node_Weight[4] = 211;
    Node_Weight[3] = 115;
    Node_Weight[8] = 7171;
    Node_Weight[9] = 701;
    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);
    odd_weight(2, 2);
    cout << "Số nút có tổng chữ số lẻ: " << sum;
    return 0;
}

Kết quả

Số nút có tổng chữ số lẻ: 2