树形 dp 介绍
概念
树形 dp，顾名思义，就是在树上做 dp，将 dp 的思想建立在树状结构之上。
常见的树形 dp 有两种转移方向：
从叶节点向根节点转移，这种也是树形 dp 中较为常见的一种。通常是在 dfs 回溯后时更新当前节点的答案。
从根节点向叶节点转移，通常是在从叶往根dfs一遍之后，再重新往下获取最后的答案。
特点
是在树上做的。
主要是在对一棵树做 dfs 时进行转移。
转移方程非常直观，但是细节较多。
套路
这个分类偏主观。
选择节点类：
无限制类：一般是点权（边权）和最大（最小）的子树的点权（边权）和。
转移方程：\(dp_u = dp_u+max/min(dp_v,0)\)（叶 \(\to\) 根，即 \(v \to u\)，\(dp_u\) 为以 \(u\) 为根节点的子树选出的最大/最小值）
有限制类：一般是子节点选了父节点就不能选。
转移方程：初始化 \(dp_{u,1}=a_u\)，\(dp_{u,1}=dp_{u,1}+dp_{v,0},dp_{u,0}=dp_{u,0}+max(dp_{v,0},dp_{v,1})\)（\(a_u\) 为 \(u\) 的点权，叶 \(\to\) 根，即 \(v \to u\)，\(dp_{u,1}\) 为选择了该节点的最大值，\(dp_{u,0}\) 代表没选该节点的最大值）
树上背包类
常见的是一件物品只有选择了它的父亲才能选择该物品。
上文提到的转移方程将会在对应的例题中推导。
习题
习题1 P1122 最大子树和
题意
对于一个树，求出其点权和最大的子树的点权和。
思路
无限制的选节点套路。
对于一个节点 \(u\)，如果其子节点 \(v\) 的子树产生了负贡献，那么不选更优，反之选更优。
#include<bits/stdc++.h>
using namespace std;
const int maxn=16000+10;
vector<int> G[maxn];
int dp[maxn],a[maxn],n,m,ans=-2147483647;
void dfs(int x,int fa){
dp[x]=a[x];
for(int i=0;i<G[x].size();i++){
int nxt=G[x][i];
if(nxt!=fa){
dfs(nxt,x);
dp[x]+=max(dp[nxt],0);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,-1);
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}
习题2 P1352 没有上司的舞会
题意
给出一棵树，每个点都有点权，现在从中选出一些节点，满足任意两点不为父子关系（即选了子节点就不能选父节点），求点权和最大值。
思路
树的最大独立集板子/带限制的选节点套路。
令 \(dp_{u,0}\) 为选 \(u\) 节点，以 \(u\) 为根的子树选出的最大值，\(dp_{u,1}\) 为不选 \(u\) 节点，以 \(u\) 为根的子树选出的最大值。
如果选了这个节点，那么这个节点的儿子节点全部不能选，即 \(dp_{u,1}=dp_{u,1}+dp_{v,0}\)，初始化为该点点权。
反之儿子节点可以选也可以不选，即 \(dp_{u,0}=dp_{u,0}+max(dp_{v,0},dp_{v,1})\)
#include<bits/stdc++.h>
using namespace std;
const int maxn=6000+10;
int n,r[maxn],root,dp[maxn][2],haveson[maxn];
vector<int> G[maxn];
void dfs(int u,int fa){
dp[u][0]=0;
dp[u][1]=r[u];
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
dfs(v,u);
//转移方程
dp[u][0]+=max(dp[v][0],dp[v][1]);//不选这个节点
dp[u][1]+=dp[v][0];//选这个节点
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>r[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;haveson[v]=1;
G[v].push_back(u);
G[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(!haveson[i]) root=i;
}
dfs(root,-1);
cout<<max(dp[root][1],dp[root][0]);
return 0;
}
习题3 P2016 战略游戏
题意
给出一棵树，选出最少的点，使得树中每条边都至少有一个端点被选。（树的最小点覆盖）
思路
令 \(dp_{u,0}\) 为不选 \(u\) 时以 \(u\) 为根的子树的最少数量，\(dp_{u,1}\) 为选 \(u\) 时以 \(u\) 为根的子树的最少数量。
如果当前节点不选，那么这个节点的所有子节点全部都要选。所以有 \(dp_{u,0}=dp_{u,0}+dp_{v,1}\)。
反之我们可以取选与不选之间最少的那个，即 \(dp_{u,1}=dp_{u,1}+min(dp_{v,0},dp_{v,1})\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1500+10;
int n,dp[maxn][2];
vector<int> G[maxn];
void dfs(int u,int fa){
dp[u][1]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v!=fa){
dfs(v,u);
dp[u][1]+=min(dp[v][0],dp[v][1]);
dp[u][0]+=dp[v][1];
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int k,sum;
cin>>k>>sum;
for(int j=1;j<=sum;j++){
int u;
cin>>u;
G[k+1].push_back(u+1);
G[u+1].push_back(k+1);
}
}
dfs(1,1);
cout<<min(dp[1][0],dp[1][1]);
return 0;
}
习题4 POJ3659 Cell Phone Network
题意
给出一棵树，如果选择了这个点，这个点和与其相邻的点都会被覆盖，求最少选多少个点能使所有点都被覆盖。（树的最小支配集）
思路
我们令 \(dp_{u,0}\) 为选择点 \(u\)，以 \(u\) 为根的子树的最小支配集，\(dp_{u,1}\) 为不选 \(u\)，且 \(u\) 被儿子覆盖时的以 \(u\) 为根的最小支配集，\(dp_{u,2}\) 为不选 \(u\)，且 \(u\) 被父亲覆盖时的最小支配集。
当我们选择 \(u\) 时，因为 \(u\) 的所有儿子都会被 \(u\) 覆盖，所以可以取最小值，即 \(dp_{u,0}=dp_{u,0}+min(dp_{v,0},dp_{v,1},dp_{v,2})\)，初始化为 \(1\)。
当我们不选 \(u\) 时：
若 \(u\) 没有被覆盖，即将要被父节点覆盖，此时可以选儿子节点支配，也可以选当前节点支配：\(dp_{u,2}=dp_{u,2}+min(dp_{v,0},dp_{v,1})\)
若 \(u\) 被覆盖，此时枚举 \(u\) 的所有子节点，选出其中之一使得代价最小：\(dp_{u,1}=min(dp_{u,1},dp_{u_k,0}+dp_{u,2}-\sum\limits^{n}\limits_{k=1}dp_{v_k,1},dp_{v_k,0})\)。
不想贴代码了。个人更偏向于贪心做法。
习题5 树的直径
题意
给出一棵树，求出其直径长度。
思路1
引入一个定理：对一棵树作 dfs，所到达的边一定为直径的一端。(证明)
那么我们对这棵树做一遍 dfs，找到一端，从这个点开始，再做一次 dfs 找到最远的那个点，这两个点之间的路径即为直径。
void dfs(int u,int fa,int dep){
if(maxdep<dep){
maxdep=dep;
pos=u;
}
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v!=fa){
dfs(v,u,dep+1);
}
}
}
好处：简单易懂
坏处：跟 Dij 一样，遇到负权边就寄
思路2
令 \(dp1_u\) 为以 \(u\) 为根的子树，\(u\) 在这棵子树内所能延伸的最长路径，\(dp2_u\) 为最长路径无公共边的次长路径。此时答案为 \(\max\limits_{i=1}\limits^{n}dp1_i+dp2_i\)。
void dfs(int u,int fa) {
d1[u]=d2[u]=0;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
dfs(v,u);
int t=d1[v]+1;
if(t>d1[u]){
d2[u]=d1[u];
d1[u]=t;
}
else if(t>d2[u]){
d2[u] = t;
}
}
d=max(d,d1[u]+d2[u]);
}
好处：能处理负权边
坏处：第一次学不知道咋实现（就像我）。
习题6 P2015 二叉苹果树
题意 by wsy
给定一棵有 \(n\) 个节点苹果树，不难发现有 \(n - 1\) 条边，第 \(i\) 边连接 \(x_i\) 和 \(y_i\)，边上有 \(z_i\) 个苹果。
现在要剪掉一些边，只保留 \(q\) 条边，问最终最多能保留多少苹果。
这棵树以 \(1\) 号节点为根，当一条边被剪掉时，这条边上深度较高的那个点的所有苹果都无法保留。
思路 bu xhr
明显的树形 DP，令 \(dp_{i, j}\) 表示 \(i\) 的子树保留 \(j\) 根树干能得到的最多的苹果数量。
令 \(ls_i,rs_i\) 为结点 \(i\) 的左右儿子，\(lc_i,rc_i\) 为 \(i\) 到左右儿子的树干的苹果数量。则 \(dp_{i,j} = \max\{dp_{ls_i, j - 1} + lc,dp_{rs_i,j-1} + rc, dp_{ls_i,k - 1} + lc + dp_{rs,j - k - 1} + rc(1 \le k \le j - 1)\}\)。
答案为 \(dp_{i,q}\)。
时间复杂度：\(O(nq^2)\)。
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int x, y;
};
int n, q, x, y, z, fa[110], h[110], dp[110][110];
bool f[110][110];
vector<Edge> v[110];
void dfs_ (int x) {
h[x]++;
for (auto [u, v] : v[x]) {
if (u != fa[x]) {
fa[u] = x, h[u] = h[x], dfs_(u);
}
}
}
int dfs (int x, int y) {
if (!f) {
return 0;
}
if (f[x][y]) {
return dp[x][y];
}
f[x][y] = 1;
int l = 0, r = 0, sl = 0, sr = 0;
for (auto [u, v] : v[x]) {
if (u == fa[x]) {
continue;
}
if (!l) {
l = u, sl = v;
}
r = u, sr = v;
}
int sum = 0, num;
for (int j = 0; j <= y; j++) {
num = 0;
if (j) {
num = dfs(l, j - 1) + sl;
}
if (j < y) {
num += dfs(r, y - j - 1) + sr;
}
sum = max(sum, num);
}
return dp[x][y] = sum;
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for (int i = 1; i < n; i++) {
cin >> x >> y >> z;
v[x].push_back({y, z}), v[y].push_back({x, z});
}
dfs_(1);
cout << dfs(1, q);
return 0;
}
