Dp In Tree
本文讲解了树形dp的一些概念和一个典型例题。
概述
树形DP（树形动态规划）是一种应用于树形结构（如树或有向无环图）的动态规划算法。其核心思想是通过递归的方式处理树的节点，逐步从树的叶子节点向根节点传递信息，从而在根节点得到最终结果。它广泛应用于图论中的路径问题、树的最优划分问题等。
树形DP的得核心是在DFS退栈时进行递推计算，推导顺序是其核心
基本步骤
- 确定状态：每个节点的状态通常与其子树的结构有关。我们需要明确对于每个节点的不同状态（如节点值、路径长度等），如何表示子问题的解。
- 状态转移：通过节点的状态来确定父节点的状态，通常通过遍历节点的子节点，将子节点的状态转移到父节点。这一步就是动态规划中的“递推”过程。
- 递归处理：一般使用深度优先搜索（DFS）进行递归，从叶子节点到根节点，计算出每个节点的状态值。
- 初始条件：叶子节点的状态通常是已知的，因为它们没有子节点，不需要状态转移。
常见应用
- 树的最长路径问题：找到树中两点之间的最长路径。可以通过递归计算每个节点为起点的最长路径，然后更新全局最长路径。
- 树的直径问题：即找出树中两点之间的最长距离。可以通过动态规划计算每个节点的最长上行路径和下行路径，最终合成得到树的直径。
- 节点的权值选择问题：有些问题要求我们选择树中部分节点的权值，比如在没有相邻节点的情况下，选取最大权值的节点集合。可以通过树形DP设计状态，判断是否选择当前节点，再递归到子节点来做选择。
例题
Acwing285 没有上司的舞会
实现
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e4;
int h[N] , e[N] , ne[N] , idx;
int happy[N] , dp[N][2] , fa[N];
void init()
{
memset(h , -1 , sizeof h);
}
void add(int a , int b)
{
e[idx] = b; ne[idx] = h[a] ; h[a] = idx++;
}
void dfs(int u)
{
dp[u][1] = happy[u];
for(int i = h[u] ; i != -1 ; i = ne[i])
{
int j = e[i];
// 先进行DFS搜索
dfs(j);
// 选择当前的节点 就只能考虑儿子都不选的情况的快乐值
dp[u][1] += dp[j][0];
// 不选当前节点 可以在任一儿子选或不选的答案中取大的那个
dp[u][0] += max(dp[j][1] , dp[j][0]);
}
}
int main()
{
init();
int n; cin >> n;
for(int i = 1 ; i <= n ; i++)
cin >> happy[i];
for(int i = 1 ; i < n ; i++)
{
int a , b;
cin >> a >> b;
add(b , a);
fa[a] ++;
}
int root = -1;
for(int i = 1 ; i <= n ; i++)
{
if(fa[i] == 0)
{
root = i;
break;
}
}
dfs(root);
cout << max(dp[root][0] , dp[root][1]);
}版权所有
版权归属：Pray0