乱讲一点基础的广义树形DP问题

DP 树形DP

写在前面的话

由于 DP 博大精深，这里只乱讲一点最简单的问题。
也是赶工的，有错误随时骂我。

三个经典的问题

树上最小支配集，最小点覆盖，最大独立集

最小支配集：选了一个点就支配了这个点和所有与这个点相邻的点，选最少的点以支配所有的点。
最小点覆盖：选了一个点就覆盖了这个点和所有以这个点为顶点的边，选最少的点以覆盖所有边。
最大独立集：选了一个点就不能选与这个点相邻的点，选最多的点且互不冲突。

显然三者是不同的，一个例子：一条长度为 $6$ 的链。

可以贪心解决， DP 的话只需大力分类讨论。
在此以最小支配集为例，另外两种也是相似的大力讨论。

例 1 树上最小支配集

状态这样设置：

$f_i$ 表示 $i$ 被儿子支配的答案
$g_i$ 表示 $i$ 被自己支配的答案
$h_i$ 表示 $i$ 被父亲支配的答案

转移呢？

初值： $f_i=inf g_i=1 g_i=0$
每次枚举每个儿子 $to$

若 $x$ 选择被自己支配，则儿子们随便取 $min$ 即可，不影响。
若 $x$ 选择被父亲支配，则儿子们都必须被儿子的儿子支配。
若 $x$ 选择被儿子支配，则儿子们至少有一个必须选择被自己支配，别的选不被父亲支配的最优解即可。

代码自己 YY 下，不困难的。

BZOJ 1596 [Usaco2008 Jan] 电话网络

形而上

形而上者谓之道，形而下者谓之器。

进一步的思考刚刚的DP过程带给了我们什么启示：
在多数情况下，一个节点唯一能影响父亲的手段即通过它与父亲的那条边，即子树内部有用的信息只有两种：

1. 子树内信息和
2. 子树根的状态

这可以帮助我们思考一些较复杂的 DP 问题。

例 2

给出一棵二叉树，节点的颜色可以是 $0,1,2$ ，父子节点、兄弟节点间的颜色不同，求最多（最少）可以有多少个点为 $0$ 色。

$n \leq 5 \times 10^5$

很简单的一道树形 DP
实际上只有是绿色和不是绿色两种状态，最大最小分别做一遍即可。
以最大为例
以 $f_{i}$ 表示点 $i$ 为绿色时这个子树中最多有多少点可以为绿， $g_{i}$ 表示点 $i$ 不为绿色时这个子树中最多多少点可以为绿。

转移是这样的，设当前节点为 $i$ ，若为绿色，则子节点必须非绿。
若不为绿色，则从两个儿子分别一绿一不绿的状态取 $max$ 转移而来。

代码被我丢 luogu 上水贡献了...
实现是非递归的，比较简洁...

BZOJ 1864 [Zjoi2006]三色二叉树

例 3

有一棵 $n$ 个节点的树，有些节点是黑的，有些节点是白的。
从树中取出一个 $x$ 个点的联通子图，使得这些点中恰有 $y$ 个黑点，判断是否存在一个合法解。

考虑尽可能优的复杂度。

有一个结论如下：对于取出确定点数的连通子图，能取到的黑点数一定是一个连续的区间。
证明：最大情况一定可以通过不断的进行删除一个相邻点，加入一个相邻点而得到最小情况，每次操作黑点个数最多有 $1$ 的变化。

所以设计如下状态： $f_{i,j,0/1}$ 表示从以 $i$ 为根的子树中取出 $j$ 个点可以得到的最大/最小黑点数，钦定选择根节点。

一个形如背包的转移：

f[x][4][0]=f[x][5][1]=(col[x]==1);
for(int i=head[x];i;i=edge[i].next)
{
    int to=edge[i].to;
    if(to==fa)continue ;
    dfs(to,x);
    for(int j=sz[x];j>=1;j--)
    for(int k=1;k<=sz[to];k++)
    f[x][j+k][0]=min(f[x][j+k][0],f[x][j][0]+f[to][k][0]),
    f[x][j+k][6]=max(f[x][j+k][7],f[x][j][8]+f[to][k][9]);
    sz[x]+=sz[to];
}
for(int i=1;i<=sz[x];i++)
{
    L[i]=min(L[i],f[x][i][0]),
    R[i]=max(R[i],f[x][i][10]);
}

每次考虑目前根与已经枚举过的子树中出几个点，新加进来的子树出几个点，合并起来。
这个复杂度看起来是 $O(n^3)$ 的...
发现一个事实，一个点对只会在他们的 $lca$ 处合并信息时被枚举到，且一个点对只会被枚举一次。
所以复杂度其实是 $O(n^2)$ 的。
这是一个常见的树形背包复杂度套路，要点在于枚举完一个子树才把它加进去。

BZOJ 5072 [Lydsy十月月赛]小A的树
原题好像是 CF 的，不记得出处了...

例 4

基环森林最大权独立集。
森林：一堆互不联通的树组成的图。
基环树：树上加一条边形成的水母一样的图。
基环树林：一堆互不联通的基环树组成的图。
最大权独立集：点有权，依旧要求满足独立集的限制。

找到这个环，随意找一条边，强制切断它，有了两个断点 $u,v$
分别强制不选，以这个点为根大力做一遍树形 DP ，显然不会影响找到最优解。

基环树 DP 常见的套路是大力断环然后再讨论断环会有什么影响，然后针对性的树形 DP 解决即可。

BZOJ 1040 [ZJOI2008] 骑士

一些更多的例题：

BZOJ 3522 [Poi2014]Hotel
BZOJ 5123 [Lydsy12月赛]线段树的匹配
BZOJ 4753 [Jsoi2016]最佳团体
BZOJ 3872 [Poi2014]Ant colony

其实题非常多，随便找找就有一大堆~