นับซับต้นไม้ขนาดคู่ใน N-ary Tree ใน C++

โจทย์

ได้รับ Adjacency List แทน N-ary Tree ทางเราต้อง นับจำนวนซับต้นไม้ (Subtree) ที่มีขนาดเป็นเลขคู่

ตัวอย่าง

Input: Tree ตามภาพ (รูท=7, มีโหนด 0,1,2,3,5,7,8,9)

Output: 4

อธิบาย: ซับต้นไม้ที่มีขนาดคู่: รูท 7, 2, 0, 3

แนวทางแก้ปัญหา

ใช้ DFS แบบ Post-order คำนวณขนาดซับต้นไม้ของแต่ละโหนด:

ขนาดโหนด = 1 + ผลรวมขนาดลูกทั้งหมด
ถ้าขนาดเป็นเลขคู่ -> เพิ่มตัวนับ
คืนค่าขนาดขึ้นไปให้ Parent

โปรแกรมตัวอย่าง

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

int countEventSizeSubTree(vector<int> adj[], int n, int v, int& EvenCount) {
    int size = 1;
    for (auto ele : adj[v])
        size += countEventSizeSubTree(adj, n, ele, EvenCount);
    if (size % 2 == 0) EvenCount++;
    return size;
}

int main() {
    int n = 10;
    vector<int> adj[n + 1];
    adj[7].push_back(2); adj[7].push_back(9);
    adj[2].push_back(0); adj[2].push_back(1);
    adj[9].push_back(3); adj[3].push_back(8); adj[0].push_back(5);
    int EvenCount = 0;
    countEventSizeSubTree(adj, n, 7, EvenCount); // เริ่มจากรูท 7
    cout << "Even Size SubTree are " << EvenCount;
    return 0;
}

ผลลัพธ์

Even Size SubTree are 4