Tree DP

Tree DP adalah dynamic programming pada struktur pohon, di mana state diasosiasikan dengan node dan transisi berasal dari anak-anak node tersebut. Karena pohon tidak memiliki siklus, urutan evaluasi alami adalah post-order traversal: proses semua anak dulu, lalu node induk. Tree DP muncul pada masalah seperti maximum independent set pada pohon, tree diameter, dan jumlah subtree yang memenuhi kondisi. Pada Chapter ini kita akan membedah pola umum Tree DP dan dua contoh klasik: maximum independent set dan tree diameter.

Aturan: Induk Bergantung pada Anak #

Pada Tree DP, dp[u] adalah solusi untuk sub-tree yang berakar di u. Karena sub-tree anak-anak independen satu sama lain, dp[u] dapat dihitung dengan menggabungkan dp[v] untuk semua anak v dari u.

State umum: seringkali dp[u] berupa pasangan (included, excluded) — solusi optimal bila u termasuk atau tidak termasuk dalam himpunan jawaban.

Mekanisme: Post-Order Traversal #

Post-order traversal menjamin: ketika kita menghitung dp[u], semua dp[v] untuk anak v sudah siap. Implementasi bisa rekursif atau iteratif dengan stack.

Kompleksitas: O(n) waktu dan O(n) ruang (untuk tabel DP), di mana n adalah jumlah node. Jauh lebih efisien daripada DP pada graph umum yang bisa O(2^n).

Contoh 1: Maximum Independent Set on Tree #

Masalah: diberikan pohon dengan nilai pada setiap node, cari subset node dengan total nilai maksimum sehingga tidak ada dua node yang berdekatan (terhubung langsung).

Insight: untuk setiap node u, ada dua pilihan:

1. Ambil u: maka anak-anak u tidak boleh diambil.
2. Lewati u: maka setiap anak v boleh diambil atau dilewati (ambil yang lebih baik).

State: dp[u][0] = maksimum bila u tidak diambil, dp[u][1] = maksimum bila u diambil.

Recurrence:

dp[u][1] = val[u] + sum(dp[v][0] for v in children(u))
dp[u][0] = sum(max(dp[v][0], dp[v][1]) for v in children(u))

Kode: Maximum Independent Set pada Tree #

#include <iostream>
#include <vector>
#include <algorithm>

void dfs(int u, int parent,
         const std::vector<std::vector<int>>& adj,
         const std::vector<int>& val,
         std::vector<std::vector<long long>>& dp) {
    dp[u][0] = 0;          // u tidak diambil
    dp[u][1] = val[u];     // u diambil
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u, adj, val, dp);
        dp[u][1] += dp[v][0];  // anak tidak boleh diambil
        dp[u][0] += std::max(dp[v][0], dp[v][1]);  // anak bebas
    }
}

int main() {
    // Pohon contoh (1-indexed):
    //     1(3)
    //    / \
    //   2(2) 3(5)
    //  / \
    // 4(4) 5(1)
    int n = 5;
    std::vector<int> val = {0, 3, 2, 5, 4, 1};  // val[0] unused
    std::vector<std::vector<int>> adj(n + 1);
    auto add_edge = [&](int a, int b) {
        adj[a].push_back(b);
        adj[b].push_back(a);
    };
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(2, 4);
    add_edge(2, 5);

    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(2, 0));
    dfs(1, 0, adj, val, dp);
    std::cout << "Maximum independent set = "
              << std::max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}

Output yang Dihasilkan:

Maximum independent set = 10

1. Baris dfs(v, u, adj, val, dp);: rekursi dulu ke anak. Post-order: anak dievaluasi sebelum induk.
2. Baris dp[u][1] = val[u];: inisialisasi bila u diambil. Nilai awal adalah val[u].
3. Baris dp[u][1] += dp[v][0];: bila u diambil, anak v harus tidak diambil. Tambahkan dp[v][0].
4. Baris dp[u][0] += std::max(dp[v][0], dp[v][1]);: bila u tidak diambil, anak v bebas (ambil yang lebih besar).
5. Hasil 10: subset optimal {3, 4, 5} dengan total nilai 5+4+1 = 10. Alternatif {1, 4, 5} juga valid (nilai 3+4+1 = 8), tetapi bukan maksimum. DP memilih yang terbaik secara otomatis.

Contoh 2: Tree Diameter #

Masalah: cari panjang jalur terpanjang antara dua node mana pun pada pohon (panjang = jumlah edge).

Insight: untuk setiap node u, jalur terpanjang yang melalui u = (dua kedalaman tertinggi dari sub-tree anak) + 2 (atau +1 bila hanya satu anak). Simpan diameter global selama traversal.

State: depth[u] = kedalaman maksimum sub-tree berakar di u (termasuk u sendiri).

#include <iostream>
#include <vector>
#include <algorithm>

int g_diameter = 0;

int dfs(int u, int parent, const std::vector<std::vector<int>>& adj) {
    int max1 = 0, max2 = 0;  // dua kedalaman tertinggi
    for (int v : adj[u]) {
        if (v == parent) continue;
        int d = dfs(v, u, adj) + 1;
        if (d > max1) {
            max2 = max1;
            max1 = d;
        } else if (d > max2) {
            max2 = d;
        }
    }
    g_diameter = std::max(g_diameter, max1 + max2);
    return max1;
}

int main() {
    // Pohon:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    //    / \
    //   6   7
    int n = 7;
    std::vector<std::vector<int>> adj(n + 1);
    auto add_edge = [&](int a, int b) {
        adj[a].push_back(b);
        adj[b].push_back(a);
    };
    add_edge(1, 2); add_edge(1, 3);
    add_edge(2, 4); add_edge(2, 5);
    add_edge(5, 6); add_edge(5, 7);

    dfs(1, 0, adj);
    std::cout << "Tree diameter = " << g_diameter << '\n';
    return 0;
}

Output yang Dihasilkan:

Tree diameter = 4

1. Baris int max1 = 0, max2 = 0;: lacak dua kedalaman tertinggi dari anak-anak u.
2. Baris int d = dfs(v, u, adj) + 1;: kedalaman dari anak v, plus 1 untuk edge u-v.
3. Baris if (d > max1) { max2 = max1; max1 = d; }: update dua terbesar. Yang sebelumnya jadi kedua.
4. Baris g_diameter = std::max(g_diameter, max1 + max2);: jalur melalui u = max1 + max2 (gabungan dua sub-jalur terdalam).
5. Hasil 4: jalur 4 → 2 → 5 → 6 (atau 7). 4 edge.

Pola Umum Tree DP #

Kode: Subtree Sum Sederhana #

#include <iostream>
#include <vector>

void dfs(int u, int parent,
         const std::vector<std::vector<int>>& adj,
         const std::vector<int>& val,
         std::vector<long long>& sum_sub) {
    sum_sub[u] = val[u];
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u, adj, val, sum_sub);
        sum_sub[u] += sum_sub[v];
    }
}

int main() {
    int n = 5;
    std::vector<int> val = {0, 3, 2, 5, 4, 1};
    std::vector<std::vector<int>> adj(n + 1);
    auto add_edge = [&](int a, int b) {
        adj[a].push_back(b); adj[b].push_back(a);
    };
    add_edge(1, 2); add_edge(1, 3); add_edge(2, 4); add_edge(2, 5);
    std::vector<long long> sum_sub(n + 1, 0);
    dfs(1, 0, adj, val, sum_sub);
    for (int i = 1; i <= n; ++i) {
        std::cout << "Subtree sum at " << i << " = " << sum_sub[i] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

Subtree sum at 1 = 15
Subtree sum at 2 = 7
Subtree sum at 3 = 5
Subtree sum at 4 = 4
Subtree sum at 5 = 1

1. Baris sum_sub[u] = val[u];: inisialisasi dengan nilai node sendiri.
2. Baris sum_sub[u] += sum_sub[v];: tambahkan total dari setiap sub-tree anak. Post-order menjamin sum_sub[v] sudah benar.
3. Hasil untuk root (node 1): total semua nilai = 3+2+5+4+1 = 15. Sesuai.

Tips Implementasi #

• Gunakan adjacency list, bukan parent pointer eksplisit — parent dilewatkan sebagai argumen dfs.
• Hati-hati stack overflow untuk pohon sangat dalam (miliaran node) — konversi ke iteratif dengan stack eksplisit.
• Bila pohon diberikan sebagai array parent p[i], konversi dulu ke adjacency list.
• Untuk rooted tree, root biasanya sudah ditentukan soal. Bila tidak, pilih node mana pun (1) sebagai root.

Ringkasan #

• Tree DP: state pada node, transisi dari anak. Post-order traversal.
• Kompleksitas O(n) — pohon tidak punya siklus.
• Maximum independent set: dp[u][0/1] dengan recurrence ambil/lewat.
• Tree diameter: lacak dua kedalaman tertinggi, update diameter global.
• Pola umum: subtree sum, tree knapsack, path counting, dll.