例1.P2015 二叉苹果树

题意简化，给定一棵带边权二叉树，去掉一些边（对应子树也会去掉）后，保留给定边数的情况下所形成的二叉树，使得二叉树边权和最大。

【思路点拨】

• 思路$1$：

本题可以将保留边转化为保留点，如果要保留 $q$ 条边，就是保留 $q+1$ 个点。 对于任意一个节点 $u$，二叉树是由左右子树构成的，那么可以定义 $f[u][k]$ 表示以 u 为根的子树中保留 $k$ 个节点的最大权值和，设 $l[u]$、$r[u]$ 分别是 $u$ 的左、右儿子。

(1)定义状态：

$f[u][k]$ 表示以 $u$ 为根的子树中最多保留 $k$ 个节点的最大权值

(2)状态转移方程如下：

$f[u][k]=\max(f[l[u]][i]+f[r[u]][k-i-1]+a[u])(0 \leq i \leq k-1)$

(3)初始化（边界）

$f[u][0]=0$

$f[u][k]=a[u](k \not=0,u为叶子即l[u]=0,r[u]=0)$

(4)$answer=f[1][q+1]$

这种方法，容易想到，但是如果题目中是多叉树怎办？一种解决方法可以将多叉树转成二叉树，感兴趣可以尝试，我们看看这种问题的一般求解思路。

---

树上背包问题

对于这种问题，就是在树上最多保留 $q$ 个点或者边，相当于规定了某一个维度上的资源上限，使得整颗子树获得最优目标收益，这就是典型的树上背包问题。

设 $f[u,i,k]$ 表示以 $u$ 为根的子树中，已经遍历了 $u$ 号点的前 $i$ 棵子树，选了 $k$ 个节点的最优收益。

转移过程结合了树形 Dp 和背包 Dp 的特点，枚举 $u$ 点的每一个子节点 $v$，同时枚举以 $v$ 为根的子树选了几个节点，将子树的结果合并到 $u$ 上。

设节点 $v$ 的儿子个数为 $Sv$ ，以 $v$ 为根的子树大小为 $size_v$，可以得到转移方程：

$f[u][i][k]=\max_{j \leq min(size_v,k)}(f[u][i-1][k-j]+f[v][Sv][j])$

直接定义三维会超时，计算 $(u,i,k)$ 状态的值，用到了 $(u,i-1,k-j)$ 的值，那可以压缩一维，将 $i$ 这一维压行压掉，$k$ 这一维就必须从大到小（与$01$背包同理）。

(1)定义状态

$f[u][k]$ 表示以 $u$ 为根最多保留 $k$ 个节点，所能获得的最大收益

(2)状态转移方程：

$f[u][k]=max_{j\leq k}(f[u][k-j]+f[v][j])$

注意转移时$k$这一维必须从大到小。

(3)边界

$f[u][0]=0$

$f[叶子][1~q]=a[叶子]$

(4)$answer=f[root][q]$

• 思路2：

设 $f[u][k]$ 表示 $u$ 的子树上保留 $k$ 条边，至多保留的苹果数目

那么状态转移方程也就显而易见了

$f[u][k]=max( f[u][k], f[u][k-j-1]+f[v][j]+dis[u][v] )$

$u$ 表示当前节点，$v$ 是 $u$ 的一个子节点

想想为什么是 $f[u][k−j−1]$ 而不是 $f[u][k−j]$？(tips:由于定义状态 $k$ 为保留边数，$u$ 到 $v$ 还要使用一条边,当然本题依然将保留边转化为保留点)

参考代码：

版本1

版本2(链式)

例2.2014 [CTSC1997]选课

【题目大意】

现在有 $n$ 门课程，第 $i$ 门课程的学分为 $a_i$，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，可能学习该课程。

一位学生要学习 $m$ 门课程，求其能获得的最多学分数。$(n,m \le 300)$

【思路点拨】

某一门课的先修课，可以看做父亲节点，要选择这门课程就必须选择父亲节点。

典型的树形背包 $Dp$ ，每门课的先修课最多只有一门（对应着树中每个节点至多只有 $1$ 个父亲），所以这 $N$ 门课构成了森林，可以新建一个“虚拟课程”- $0$ 号节点，把包含$N$ 个节点的森林转化为包含 $N+1$ 个节点的树，其中节点 $0$ 为根节点。

设 $F[u][k]$ 表示以 $u$ 为根的子树中选$k$门课能够获得的最高学分

$F[u][k]=max(F[u][k],F[v][j]+F[u][k-j])$

这是优化后背包，$k$ 就必须从大到小

最终答案是 $F[0][m+1]$

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> G[1010];
int a[1010],f[1010][1010];
void dfs(int u){
    f[u][0]=0;
    f[u][1]=a[u];
	for(auto v:G[u]){
		dfs(v);
		for(int j=m;j>1;j--)  //复杂度不优秀
			for(int k=1;k<j;k++)
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
		}
}
int main(){
	cin>>n>>m;
	m++;
	for(int i=1;i<=n;i++){
		int u;
		cin>>u>>a[i];
		G[u].push_back(i);
	}
	dfs(0);
	cout<<f[0][m];
	return 0;
}

复杂度是 $O(n*m^2)$ ,可以进行上下界优化，复杂度可以优化到 $O(n*m)$.

树上背包优化

实际合并子树，并不需要 $j$ 每次都从 m 开始，$j$ 实际就是前面子树的大小，逐渐增加，那么可以用 siz 数组逐渐合并子树，时间复杂度是 $O(n*m)$ ,详细证明请参考 树上背包复杂度证明

U53204 【数据加强版】选课

需要使用 vector,否则会 MLE

参考代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int> > G;
vector<vector<int> > f;
vector<int>a,siz;


void dfs(int u){
    f[u].resize(m+1);  //扩展u的大小

    f[u][0]=0;
    f[u][1]=a[u];
    siz[u]=1;
	for(auto v:G[u]){
        
		dfs(v);
        siz[u]+=siz[v];

		for(int j=min(m,siz[u]);j>1;j--)  //复杂度 O(nm)
			for(int k=max(1,j-(siz[u]-siz[v]));k<=min(j-1,siz[v]);k++)
        // k 是有下界的 例如当前整个树 siz[u]=15 ,siz[v]=5,那么之前只求过 f[1...10] , k 不能太小，k 太小 k=1 ,就需要 f[14] ,之前没有算过，没有意义 
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
		}
}
int main(){
	cin>>n>>m;
	m++;
    G.resize(n+1); a.resize(n+1);
    f.resize(n+1); siz.resize(n+1);

	for(int i=1;i<=n;i++){
		int u;
		cin>>u>>a[i];
		G[u].push_back(i);
	}
	dfs(0);
	cout<<f[0][m];
	return 0;
}

例2.1273 有线电视网

【题意简化】给定一棵带边权的树（边权是代价），叶子节点带点权（收益），保证不亏损的前提下，保留叶子节点越多越好。

思路点拨：

保留叶子结点的数量，维护总代价，如果这个代价大于零，就满足要求，那么找到最大保留叶子节点数量（总代价为正）就可以了。

定义 $f[u][j]$ 表示以 $u$ 为根，有 $j$ 个叶子节点，所能获得的最大价值。

显然转为为了树上背包问题

$f[u][j]=max(f[u][j-k]+f[v][k]-dis(u,v))$

$j$ 要从大到小枚举。 最后 $i$ 从大到小枚举，第一个 $f[1][i]$ 大于零时，输出 $i$，就是答案。

参考代码：点击

例3.P1272 重建道路

【题意简化】给定一颗树，删除最少得边，使得一个大小为 $p$ 的子树与其他部分分离，求最少删除的边数。

【题解】

获得大小为 $p$ 的子树 , 那么这个子树的根可以是任意节点。定义 $f[x][p]$ 表示以 $x$ 为根的子树中，要保留 $p$ 个节点最少删除的边数。

$f[x][p]=min(f[x][p-j]+f[y][j]-1)$

$f[x][1]=儿子数量$

$ans=min(f[root][p],f[x][p]+1)$ //对于非根的子树需要删除其父亲方向上的一条边。

参考代码：U53878 【数据加强版】道路重建 参考代码

例4.P3177 [HAOI2015]树上染色

【题意简化】

给定一颗 $n$ 个节点带边权的树，将其中 $k$ 个节点染成黑色，其余染成白色。求所有同色点之间的距离和的最大值。

【题解】

树上保留 $k$ 个点，想到了树上背包，同色点之间的距离和，可以考虑每条边对答案的贡献。

$f[u][m]$ 表示以 $u$ 为根的子树，保留 $m$ 个黑点，子树内所能获得的最大收益。

$f[u][m]=max(f[u][m-j]+f[v][j]+tot*w[u][v])$

$u$ 为子树 $v$ 中保留 $j$ 个黑点，$tot$ 表示边 $(u,v)$ 被同色使用的次数; $u$ 的一个儿子 $v$ ，边 $(u,v)$ 被使用的次数为两边同色点的乘积 ;

$tot=(k-j)*j+(n-size[v]-(k-j))*(size[v]-j)$

注意：典型树上背包，$m$ 要从大到小;

例5.P4516 [JSOI2018]潜入行动

【题意简化】

给定一颗 $n$ 个节点的树，一个节点上可以放置 $1$ 个监听设备，监听设备可以监听除本节点外的邻居节点。在树上刚好放置 $k$ 个监听设备，保证所有节点被监听，求放置的方法数。

【题解】

考虑点 $x$ 放或者不放监听设备，可以使用一维 0/1 状态表示。要求所有点被监听，为了计数不重不漏，再使用一维 0/1 表示 $x$ 是否被儿子监听到 。

定义状态：f[x][k][0][0/1] 表示 $x$ 的子树中安装 $k$ 台设备,$x$ 子树内都被被监听到, $x$ 点处没有安装监听，$x$ 未被/被儿子监听 , f[x][k][1][0/1] 表示 $x$ 处安装了设备。

分情况讨论:

1. $x$ 没有安装，没被监听 . $y$ 不能安装, $y$ 必须被监听

   $f[x][i][0][0]=\sum f[x][i-j][0][0]*f[y][j][0][1])$

2. $x$ 没有安装，被监听 . $y$ 分两种情况：

   (1) $x$ 之前儿子未监听 $x$ 的方法数 $\times$ $y$ 监听 $x$ ;

   $f[x][i][0][1] +=f[x][i-j][0][0]*f[y][j][1][1]$

   (2) $x$ 之前儿子监听 $x$ $\times$ ($y$ 监听 $x$ + 不监听 $x$ )

   $f[x][i][0][1]+=f[x][i-j][0][1]*(f[y][j][0][1]+f[y][j][1][1])$

3. $x$ 安装, 未被监听. $y$ 不能安装 , $y$ 可能被监听或不被监听

   $f[x][i][1][0]=\sum f[x][i-j][1][0]*(f[y][j][0][0]+f[y][j][0][1])$

4. $x$ 安装,被监听 . $y$ 分两种情况：

   (1) $x$ 之前儿子未监听 $x$ $\times$ ( $y$ 安装了监控 被监听 + 不背监听 )

   $f[x][i][1][1]+=f[x][i-j][1][0]*(f[y][j][1][0]+f[y][j][1][1])$

   (2) $x$ 之前儿子监听 $x$ $\times$ ( $y$ 可安装/不安装 + 被监听/不被监听)

   $f[x][i][1][1]+=f[x][i-j][1][1]*(f[y][j][0][0]+f[y][j][0][1]+f[y][j][1][0]+f[y][j][1][1])$

注意事项：

1. 由于空间限制数组需要定义为 int ，中间计算转化为 long long .
2. 计数求和需要将前面计算的 f 值清空，临时需要数组缓存。
3. 如果使用查表法，需要规定内层循环下限。

具体可查看参考代码： P4516 [JSOI2018]潜入行动 参考代码

---

学习完毕

{{ select(1) }}

• YES
• NO