树形dp

树上最大独立集问题

树形dp最经典的问题。

问题详情

一句话：给一棵大小为 $n$ 的树，求最大点权独立集。

先来看一下啥是独立集，再考虑最大点权的问题。

选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。

**最大点权：**即在所有可能存在的独立集中，点权之和(若没有点权，则认为所有点的点权都是$1$)最大的称为最大点权独立集。

聪明的你立刻联想到了最大独立集=最大匹配！

醒醒，二分图匹配没有点权。

因此，我们要使用dp思想！

首先，解决第一个问题——很可能题目并没有指定根节点($root$)，而仅仅给了你一个无向连通图($n$ 个节点 $n-1$ 条边，保证任意两两节点连通)

我们直接任意选择一个作为根($root$)不就完了嘛！就是这么简单粗暴

对于整个大问题，dp就是不断求解一个个小问题的过程。

对于任意一个节点，状态只有两种：

1. 在最大点权独立集中。
2. 不在最大点权独立集中。

因此，我们用 $dp[i][0]$ 表示节点 $i$ 不在独立集中时以节点 $i$ 为根的树的最大点权独立集；用 $dp[i][1]$ 表示节点 $i$ 在独立集中时以节点 $i$ 为根的树的最大点权独立集。

状态转移方程: $$ \begin{aligned} &dp[i][1]=\sum dp[son[i][a]][0]\space+val[i] \&dp[i][0]=\sum max(dp[son[i][a]][0],dp[son[i][a]][1]) \end{aligned} $$ $son[i][a]$ 记录节点 $i$ 的儿子。

如果节点 $i$ 在独立集中，则 $i$ 的任何儿子一定不在独立集中。因此，我们只需要把以 $i$ 的儿子们为根且根节点不在独立集中的最大独立集求和再加上节点 $i$ 的点权，就得到正确的解。

而如果节点 $i$ 不在独立集中，则 $i$ 的儿子在与不在均可。因此，我们要把以 $i$ 的儿子们为根的最大独立集(因此要在根节点在和不在两个中取最大值)求和即可。

而dp完成后，可得到 $ans=max(dp[root][0],dp[root][1])$。

至于如何遍历一棵树，当然是DFS！

install APPs！

众所周知(就算你不知，现在也知了)，背包是可以挂在树上的。

433大大的疑惑：现在，433明白，自己需要 $n$ 个软件，并且假设她清楚每个软件所需要的安装时间 $w[i]$ 以及实用价值(搞完之后$jj$们能获得的满足感) $val[i]$ (虽然但是这并不可能)，而她因为要练习~~(不，因为烦躁)~~，只有 $m$ 的时间来搞这些事情(否则将因个人原因摧残与迫害电脑)。但是，众所周知(虽然但是可能433不知)，某一些软件依赖于其他软件(这里，我们规定若存在依赖，有且仅有一个依赖项)，如：美颜相机依赖于摄像头驱动——一种433不会搞的东西($jj$们为此卖力的教)，所以，安装任何软件之前，都应确保其依赖的软件全部安装。问能取得的最大价值是多少。

由上述问题我们发现，软件之间具有依赖关系，一般地，某个物品的依赖物品只有一个~~(如果有多个的话可以考虑把出题人挂在树上)~~(但某个物品可以同时被多个物品依赖)，且依赖关系可以表示为一棵树：如果选择一个物品，则必须选择它的父节点。

比如，若我们规定 $a$ 依赖于 $b$ 表示为 $a\rightarrow{b}$，则 $$ b\rightarrow{a} \newline c\rightarrow{a} \newline d\rightarrow{a} \newline e\rightarrow{b} \newline f\rightarrow{b} \newline g\rightarrow{c} $$

可以用下图表示：

思路

背包和树形dp结合，转化为分组背包问题。

首先，我们明确，进行树形dp时我们是从下至上进行的，因此我们对节点 $i$ 进行状态转移时，节点 $i$ 的所有儿子的dp值是已知的。

$dp[i][j]$ 表示以节点 $i$ 为根的树中背包容量为 $j$ 时所能取得的最大价值。

由图的意义我们可以得知，如果要选择以节点 $i$ 为根节点的树中任意一个节点，都必须选择节点 $i$ (必须按照深度逐一装)。

因此，留给节点 $i$ 的儿子们的空间只有 $j-w[i]$。我们要在节点 $i$ 的 $k$ 个儿子中，每个儿子分配 $t_k$ 的背包空间，使得 $\sum_{a=1}^kdp[son[i][a]][t_a]\space|\sum_{a=1}^kt_a=j-w[i]$ 最大。

对此，我们直接进行三重循环即可。因此，时间复杂度为 $O(n^3)$。

环

我们知道一般图上是无法dp的。因为图上的环会导致循环转移，即存在后效性(求出的dp值可能不正确)。这在dp问题中是不允许存在的。

一般图转化为无环图的主要方法是将强连通分量缩成一个点。

依赖性背包中的强连通分量就是一个环。环中的每个点或者全选，或者全不选，因此可以缩点。

将强连通分量中的每个点的重量求和作为新点的重量，价值求和作为新点的价值。

剩下的就是依赖性背包板子了。

最后的一点儿

我们将所有依赖关系连边之后就形成一张图。

如果没有“循环依赖”关系（即环），这些依赖关系就形成若干棵外向树，即外向树森林。

建立虚拟根节点，价值和重量均为 $0$，并将所有没有依赖的物品都与 $root$ 连边，则转化为一棵外向树。

基环树上的dp

首先

在学习基环树上的dp之前，就得先把标题看懂——了解奇环树是啥。

奇环树，就是：

1. 在一棵树上增加一条边。
2. 个树上有一个环。
3. 有 $n$ 个点和 $m$ 条边的无向连通图。

奇环树的情况：

• 无向
• 有向
  1. 基环外向树(每个点只有一条入边)。
  2. 基环内向树(每个点只有一条出边)。

因为奇环树的边数 $-1$ 便形成了一棵树，因此仍将其视作”树”来解决问题。

（没看懂）每个点只和一个点连边所形成的无向图一定是一片基环树森林。

对于这种恶心的树，我们也采取一种暴力的手段来对付，就是在环上任意删一条边，然后转化为一棵树，跑树形dp即可。

找环

不管你对于出题人命制的题目有多大的意见~~(tmd，为神魔有环——优美中国话)~~，你都得一步步来——先找到环。

找到一条边即可，不需要记录所有环上节点。

1. 无向图：

   1. 你飞速的撸出了一窜拓扑排序的模板。
   2. 接着，恭喜，环找到了。(入度 $\ge{2}$ 的点就是环上的点，和上一个被访问的点之间的边一定是环边)

2. 有向图：

   1. 你疯狂的搞出了一份DFS标准模板，调试完成。
   2. 恭喜，环也找到了。(DFS时若某一个节点被访问第二次，即是环上的点，和上一个被访问的点之间的边一定是环边)

round $1$

但是注意，当我们删去边 $u\rightarrow{v}$ 并以节点 $u$ 为根跑树形dp后，虽然进行了删边操作，但实际上是有的，因此节点 $u$ 和节点 $v$ 仅能选择其中一个，从而出现两种情况：

1. $dp[u][0]$ 表示强制不选节点 $u$，因此对于节点 $v$ 是否选择无限制，此情况一定成立。
2. $dp[u][1]$ 表示强制选择节点 $u$，这时候节点 $v$ 必定不可以选择，但是我们并不清楚节点 $v$ 的选择情况，所以这个dp值在某些情况下是错误的，不能取。

$dp[u][0]$ 对于节点 $u$ 和 $v$ 的选和不选两种状态的覆盖情况为：

节点	选	不选
$u$	$\times$	$\checkmark$
$v$	$\checkmark$	$\checkmark$

因此，我们需要考虑一下一定选择 $u$ 节点的情况，因此，我们以节点 $v$ 为根再跑一遍树状dp，而 $dp[v][0]$ 就包含了选择节点 $u$ 的情况。

最后，我们需要在两种情况下选择较大值 $max(dp[u][0],dp[v][0])$ 即可。

round $2$

对于这个选与不选的问题，还有一种思考的维度。

我们考虑节点 $u$ 可能的两种情况：

1. $dp[u][0]$ 强制不选，这时对节点 $v$ 的状态没有要求，不做处理，正常跑dp即可。、
2. $dp[i][1]$ 强制选择，这时节点 $v$ 必须不选，因此，再跑一次dp，将 $dp[v][1]$ 初始化为 $-\infty$ (表示不存在这种情况，进行dp时是不会选择如此不好的节点的，强制保证了不选节点 $v$)。

外向DAG

每个点都有且只有一个入度，并且环内的节点方向指向环外，因此任何一个点沿着唯一入边走都会走到环上。

内向DAG

每个点都有且只有一个出度，并且环外的节点方向指向环内，因此任何一个点沿着唯一出边走都会走到环上。

有向无环图(DAG)上的dp(拓扑序dp)

因为有向无环图有拓扑序，所以我们按拓扑序转移即可保证无后效性(即改变已经访问过的节点)。

DAG上的dp可以在 $O(n+m)$ 的时间复杂度内解决DAG上最短/最长路、最短路计数等基本问题。

其他应用(一些奇怪的题的题解)

有时间再补