树形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 - 博客园