本篇主要以总结为主 较有基础食用更加
ps 本篇不涉及题的讲解 如有需要请看 树形dp习题精讲
目录
树形dp
换根dp
树上背包
0.前置知识
$\space\space\space\space\space$ 树形dp是基于dfs 我们在此处先稍微介绍下 dfs的一些逻辑
$\space\space\space\space\space$ 众所周知 dfs 的遍历共只有两种 一种分为自顶向下更新 一种为自底向上更新 而对于一般的遍历框架
void dfs(int u, int father) //u通常是父节点 而v通常是子节点
{
if special
do sth; //如果有什么需要进行的特殊操作 比如初始话 或者判断等等
for(int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if(v == father) continue; //我们只向叶子节点方向遍历
do dp; // 此处是先更新在进行递归 所属于自顶向下更新 用父节点更新子节点
dfs(v, u);
do dp; //此处是先递归在更新 所属于自底向上 开始用子节点的信息 更新父节点的信息
}
do dp3; //此处是对每一个根节点已经遍历完了其所有的子节点后进行的操作
//通常是用于对以u为根节点的子树的操作
}
1. 树形dp
1.1 什么是树形dp
$\space\space\space\space\space$ 众所周知,树是一个有 n 个节点,n−1 条无向边的图。这种图可以表示一些事物之间的关系,且这种关系是联通的、无环的。当动态规划建立在一种依赖关系(或者其它互相的关系)之上,树形 dp 便是解决这类问题的好帮手。
$\space\space\space\space\space$通常对于树上的每一个节点,我们要求的 dp 的值通过其父亲节点/儿子节点推算过来。对于特殊的节点(根节点、叶子节点),有时需要初始化。
$\space\space\space\space\space$这样泛泛而谈并不能让我们深入了解树形 dp,让我们来看树形 dp 的架构与习题。
1.2 树形dp的架构
$\space\space\space\space\space$ 先说建边
$\space\space\space\space\space$ 通常来说 我们的建边的目的是为了给每个枚举的点找到一条通往叶子节点的路径(为了避免成环 我们人为规定只向叶子节点遍历 如果要向根节点遍历就涉及换根dp) 换言之 是因为题意所给的是两点的关系(并不一定是根->叶子节点) 此时为了便于遍历 我们需要进行双向边 使其在进行点的遍历时候能够走到叶子节点 这也是大多数题的建边方式 而在给定如 战略游戏 类的边的情况 已经人为规定了一条根节点到叶子节点的方向 所以我们仅仅单向边即可
$\space\space\space\space\space$ 再说基本框架
void dfs(int u, int father) //u通常是父节点 而v通常是子节点
{
if special
do sth; //如果有什么需要进行的特殊操作 比如初始话 或者判断等等
for(int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if(v == father) continue; //我们只向叶子节点方向遍历
dfs(v, u);
do dp; //自底向上 开始用子节点的信息 更新父节点的信息
}
}
1.3 树形dp的常规应用
2.换根dp
2.1 什么是换根dp
$\space\space\space\space\space$ 换根dp是一种比较难以理解的dp 我们先来看下 常规的dp有哪些缺陷 在常规的dp中 因为我们是避免死循环人为规定了一种遍历方向 但这种人为的方向后 却不能直接便于更新所有由父节点转移过来的信息 (可以更新 但需要将其转化为根节点进行从0开始更新 如果需要暴力枚举所有点进行这样更新 很容易导致tle) 所以我们需要想办法使得父节点->子节点的信息更快的更新
换根dp一般分为三个步骤
1、先指定一个根节点
2、一次dfs统计子树内的节点对当前节点的贡献
3、一次dfs统计父亲节点对当前节点的贡献并合并统计最终答案
$\space\space\space\space\space$ 为什么换根dp可以更快的更新 我们发现 对于根节点u - > 子节点 v的转移来说 并不是所有的的到u与到v的信息截然不同 我们完全可以利用这些信息 进行一个差价的弥补 进而进行信息的更新
2.2 换根dp的基本框架
f[u]; //在整个树中 以u为根节点的信息和
g[u]; // 以u为根节点的子树中对u的信息和
sz[u]; // 统计以u为根节点的子树的大小
void dfs_p(int u, int father) //u通常是父节点 而v通常是子节点 此处 以u为根节点的子树中的信息
{
if special
do sth; //如果有什么需要进行的特殊操作 比如初始话 或者判断等等
for(int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if(v == father) continue; //我们只向叶子节点方向遍历
dfs(v, u);
do dp; //此处是先递归在更新 所属于自底向上 开始用子节点的信息 更新父节点的信息
}
}
void dfs_u(int u, int father) //u通常是父节点 而v通常是子节点 此处逐渐的用父节点的信息更新子节点
{
if special
do sth; //如果有什么需要进行的特殊操作 比如初始话 或者判断等等
for(int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if(v == father) continue; //我们只向叶子节点方向遍历
do dp; //此处是先更新在递归 所属于自顶向下 开始用父节点的信息 更新子节点的信息
dfs(v, u);
}
}
3.树上分组背包
3.1 什么是树上分组背包
$\space\space\space\space\space$ 物品的依赖关系往往以树的形式进行存在 如果最后的关系是一棵树 那么通常的根节点则为1 如果最后形成的是个森林 我们往往可以新建一个虚拟根节点0 通过这个根节点进行其他节点的联系 在通常的树上分组背包中 f[u][k] 表示在以u为根节点 进行k次选择的集合(集合属性通常是最值) 我们进行递归自底向上更新 我们将每个子树v看做一个组 在组内进行0 -> k(k <= min(sz[v], m)决策 (sz是以v为根节点的子树大小 而m则是通常可以供选择的体积上限) 每一种k的划分选择看成一种决策 进而通过转移方程进行更新
通常的转移方程为 f[u][k] = min(f[u][k], f[u][j - k] + f[v][k] + val)
$\space\space\space\space\space$ f[u][k] 不难理解 f[u][j - k]需要注意的是 因为我们的递归遍历 所以在枚举v这个子树的时候 我们的f[u][j - k] 实则意思为 在以u为根节点 排除v这个子树选择j - k 个的最值(因为我们枚举到v 到还没有进行更新) 而f[v][k]则已经被更新过了 此处则代表的是一个值 即以v为根节点 选择k个的值 最后的val 便是某些需要处理的情况值了 具体看情况而定
3.2 树上分组背包的框架
void dfs(int u, int father) //u通常是父节点 而v通常是子节点 此处 以u为根节点的子树中的信息
{
if special
do sth; //如果有什么需要进行的特殊操作 比如初始话 或者判断等等
for(int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if(v == father) continue;
dfs(v, u);
for(int j = m; j >= 0; j --) //枚举体积上限
for(int k = 0; k < min(j, m); k ++) //枚举决策上限 m代表可枚举的上限(通常是题意给出)
f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + w[i] + val);//val 是由题意需要计算的转移额外值
}
}
tql