树形DP讲解

树形DP讲解

一、引言

树形动态规划（Tree DP）是动态规划中的一种特殊形式，它专门用于解决与树结构相关的问题。树形DP的核心思想是利用树的分形结构，递归地定义和解决问题。在这篇文章中，我们将深入探讨树形DP的基本概念、经典例题以及实际应用。

二、树形DP基础

1、树的定义

在图论中，树被定义为一个连通且无圈的图。树的分形结构意味着树的每个子树也是一棵完整的树，这使得树形DP天然适合递归求解。

2、树形DP的基本思想

树形DP通常遵循“先子树后合并”的原则，这与树的后序遍历相似。我们先递归访问所有子树，然后在根节点上合并结果。

3、代码示例：子树大小

void dfs(int u) {
    if (u 是叶子) {
        f[u] = 1;
        return;
    }
    for (int v : e[u]) {
        dfs(v);
        f[u] += f[v];
    }
    f[u] += 1; // 本身
}

这段代码通过深度优先搜索（DFS）计算以每个节点为根的子树大小。

三、经典例题解析

1、树的平衡点

平衡点是指删除树中的某个节点后，使得剩下的连通块中最大的连通块大小最小。我们可以通过计算每个节点的子树大小来找到平衡点。

1.1、代码示例

import java.util.ArrayList;
import java.util.List;

public class Main {
    static final int N = 100010; // 假设N是图的最大节点数
    static List<Integer>[] e = new ArrayList[N];
    static int ans, idx, f[] = new int[N];

    public static void main(String[] args) {
        // 初始化邻接表
        for (int i = 0; i < N; i++) {
            e[i] = new ArrayList<>();
        }
        // 示例调用
        int root = 1; // 假设1是树的根节点
        int fa = 0; // 根节点没有父节点
        dfs(root, fa);
        System.out.println("最大值: " + ans + ", 节点: " + idx);
    }

    static void dfs(int u, int fa) {
        f[u] = 1;
        int mx = 0;
        for (int v : e[u]) {
            if (v == fa) continue;
            dfs(v, u);
            f[u] += f[v];
            mx = Math.max(mx, f[v]);
        }
        mx = Math.max(mx, n - f[u]);
        if (ans < mx) {
            ans = mx;
            idx = u;
        }
    }

    // 假设n是节点总数
    static int n = 10; // 这里需要根据实际情况设置
}

2、没有上司的舞会（树的最大独立集）

在这个问题中，我们需要找到树的最大权值独立集，即没有直接上司和下属关系的节点集合。

2.1、代码示例

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static final int N = 10000 + 10;
    static ArrayList<Integer>[] tr = new ArrayList[N];
    static int[][] f = new int[N][2];
    static int[] v = new int[N];
    static int[] Happy = new int[N];
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 初始化邻接表
        for (int i = 0; i < N; i++) {
            tr[i] = new ArrayList<>();
        }

        n = scanner.nextInt();
        for (int i = 1; i <= n; ++i) {
            Happy[i] = scanner.nextInt();
        }

        for (int i = 1; i < n; ++i) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            tr[y].add(x);
        }

        int root = 0;
        for (int i = 1; i <= n; ++i) {
            if (v[i] == 0) {
                root = i;
                break;
            }
        }

        dfs(root);
        System.out.println(Math.max(f[root][0], f[root][1]));
    }

    static void dfs(int u) {
        f[u][0] = 0;
        f[u][1] = Happy[u];

        for (int v : tr[u]) {
            dfs(v);
            f[u][0] += Math.max(f[v][0], f[v][1]);
            f[u][1] += f[v][0];
        }
    }
}

四、总结

树形DP是一种强大的算法工具，它通过利用树的结构特性来解决复杂的优化问题。通过本文的介绍和代码示例，我们可以看到树形DP在解决树相关问题时的效率和优雅。掌握树形DP不仅能够提升算法设计能力，还能在实际问题中找到创新的解决方案。

---

版权声明：本博客内容为原创，转载请保留原文链接及作者信息。

参考文章：

• 【动态规划】树形DP完全详解！ - RioTian - 博客园