树形DP总结

标签：总结

序

做了一段时间的树形DP了，还是总结一下这类DP的套路吧，以便以后的复习与理解。

核心思想

树形DP的核心思想就是利用DFS进行递归求解。即通过DFS一直递归直到叶子结点，然后一层一层的处理并返回最优值。

题目类型

一.基础树规

这类题转移较为明显，一般能较快设计出状态，然后按照DFS一层一层转移即可。

二.树的最小支配集，最小点覆盖与最大独立集

最小支配集：

从V中选取尽量少的点组成一个集合，让V中剩余的点都与取出来的点有边相连。
（点）

最小点覆盖：

从V中选取尽量少的点组成一个集合V1，让所有边(u,v)中要么u属于V1，要么v属于V1
（边）

最大独立集：

从V中选取尽量多的点组成一个集合，让这些点中间没有边项链，也就是说对于任何一条边，u,v不能同时属于集合V1.
关于解法详见joeylee97和Ashly两位大佬的博客

三.换根DP

这类题目一般做法是要枚举所有点作为根节点，对每个根节点取最大（最小）值才能得到答案。
不过肯定要超时，所以我们这里采用：换根法+二次扫描法。
大概步骤：
1.任取一个点为根节点（如：1），然后进行一次DP得到以1为根节点的最优值。
2.再以1为根节点往下遍历，遍历到任意一个节点x后，把x当做根节点，然后把x的父亲及其以外的节点当做x一颗子树进行转移。
下面来看一道例题：

最大疯子树
【题目描述】
给定一棵 n 个结点的树，结点编号为 1~n，i 号结点的权重记为 wi（每个点的权值各不相同）。我们定义一个“疯子树”为：
1 是一个联通子图。
2 我们将子图内的点按照权重从小到大排序后序列为 b1,b2,…,bm，对于任意的i，bi到 bi+1最短路径（不含 bi和 bi+1）上的结点的权值都小于等于w_bi 。
输出包含结点最多的“疯子树”的结点数。
【输入格式】
数据有多组 case,文件以 EOF 结束，每组第一行输入一个 n 表示树的节点数；
接下来一行包含 n 个整数，第 i 个数表示 i 号结点的权重 wi；接下行 n-1 行，第
i 行包含 2 个整数 ui, vi，表示 ui和 vi有一条边。
【输出格式】
对于每组 case 输出一行，包含一个整数，表示包含结点最多的“疯子树”
的结点数。
【样例输入】
5
1 4 2 3 5
1 2
2 3
3 4
4 5
5
2 5 4 1 3
1 2
2 3
3 4
4 5
【样例输出】
4
4
【数据范围】
对于 10%的数据有所有组的 n 之和 n≤20。
对于 30%的数据有所有组的 n 之和 n≤2000。
对于 100%的数据有所有组的 n 之和 n≤200000，0 < wi≤100000000，n 为正整数。
这道题似乎是电子科大的春令营考试题目（当时去考试，没记错应该是爆0了…）
首先考虑一条链的情况，可以发现我们选取的这段区间必须满足先降序后升序的情况，也可以这样理解，以点x为分割点，x往左边和往右边都是升序的情况。（上里及下面所说的升序降序都是不严格的）
在纸上画一下大概是凹形那种样子…
然后我们再来考虑树，如果以节点x为分割点，那么以x为根节点，往下遍历的合法点必须是升序的。
所以得到一个n^2的算法，枚举每一个点为根节点，往下遍历所能得到的最大升序子图。

f[x] = 1;
for(int i = head[x]; i; i = e[i].next)
{
    if(e[i].to == fa) continue;
    dfs(e[i].to);
    if(w[e[i].to] >= w[x]) f[x] += f[e[i].to];
}

然后我们考虑优化：用换根法+二次扫描法
第一次以1为根节点得到f[x]表示以x为根节点的子树的最优值。
第二次再从1出发，当遍历到x节点时，把x节点当做根，父亲及相连的节点当做另一颗子树，那么如果w[x]<=w[fa]，那么f[x]+=f[fa]，否则不做处理。这样我们就换根成功了。
相关题目:
POJ3585 Accumulation Degree
hdu2196 Computer