Chuyển cây thành rừng các nút chẵn trong C++

Cho cây nhị phân N nút. Tính số cạnh tối đa có thể xóa để được rừng (forest) chỉ chứa các cây có số nút chẵn.

Chương trình C++

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

// Trả về số nút của cây con có gốc node
int depth_search(vector<int> tree[N], int visit[N], int *ans, int node) {
    int num = 0, temp = 0;
    visit[node] = 1;  // Đánh dấu đã thăm
    
    for (int i = 0; i < tree[node].size(); i++) {
        if (visit[tree[node][i]] == 0) {
            temp = depth_search(tree, visit, ans, tree[node][i]);
            // Nếu số nút chẵn, tăng số cạnh cần xóa
            (temp % 2) ? (num += temp) : ((*ans)++);
        }
    }
    return num + 1;
}

int print_maxedge(vector<int> tree[N], int n) {
    int visit[n + 2];
    int ans = 0;
    memset(visit, 0, sizeof visit);
    depth_search(tree, visit, &ans, 1);
    return ans;
}

int main() {
    int n = 10;
    vector<int> tree[n + 2];
    // Xây dựng cây (danh sách kề)
    tree[1].push_back(3); tree[3].push_back(1);
    tree[1].push_back(6); tree[6].push_back(1);
    tree[1].push_back(2); tree[2].push_back(1);
    tree[3].push_back(4); tree[4].push_back(3);
    tree[6].push_back(8); tree[8].push_back(6);
    tree[2].push_back(7); tree[7].push_back(2);
    tree[2].push_back(5); tree[5].push_back(2);
    tree[4].push_back(9); tree[9].push_back(4);
    tree[4].push_back(10); tree[10].push_back(4);
    
    cout << print_maxedge(tree, n) << endl;
    return 0;
}

Kết quả

2

Giải thích

DFS từ gốc, tính kích thước mỗi cây con. Nếu cây con có số nút chẵn, có thể cắt cạnh nối nó với cha (tăng ans). Kết quả là số cạnh có thể cắt để tất cả cây con còn lại đều có số nút chẵn.