【高级算法】树形DP

前言

本篇文章针对对于树形DP有一定基础的人，没学过的话请出门左转~

树上背包

P1273 有线电视网

题目简述

有一棵有根树，每个叶子节点都有一个可赚的钱数，每走一条路都有相应的花费。

则在不亏本的情况下从根节点能到达至多几个叶子节点？

思路

嗯对大概就是一道经典的树上背包问题，我们做动态规划的第一步就是确定状态，便于我们列出状态转移方程。

那么我们就规定 $dp[i][j]$ 表示以节点 $i$ 为根，往下找 $j$ 个叶子节点的最大价值。那么最终的答案就是 $dp[1][j](0 \le j \le m)$ 大于等于 $0$ 中的最大的 $j$。

可能一会有疑惑——我们不是要让花的钱最少吗？为什么要求最大值？注意，我们求的是最大价值。

我们用 $mon[i]$ 表示节点 $i$ 可以赚到的钱，那么当节点 $i$ 到 $j$ 的花费为 $k$ 的时候，此时的 $mon[j]$ 就应该减去 $k$ 而不是加上。而到叶子节点的时候我们应该加上它本身能赚的钱，这样我们的花费就初始化好了。

然后是初始化，我们先对这个节点按后序遍历重新编号，然后对 $dp[i][j]$ 初始化为极小值。

接下来考虑状态转移方程，对于 $dp[i][j]$ 有两种不同的情况：

当节点 $i$ 为叶子结点的时候，此时不难得出状态转移方程为

$$dp[i][j] = \max(dp[i-1][j-1]+mon[i],dp[i-1][j])$$

那么当 $i$ 为非叶子节点时呢？我们有选和不选两种情况：

如果我们选的话可以得出 $dp[i][j] = dp[i-1][j]+mon[i]$ 的式子。

而如果不选呢？那么它的子树也不能选了！所以我们还要记录节点的子树大小。

所以得出了 $dp[i][j] = dp[i-siz[i]][j]$ 这个式子。

最后结合一下：

$$dp[i][j] = \max(dp[i-1][j]+mon[i],dp[i-siz[i]][j])$$

最后我们看时间复杂度为 $O(mn)$，所以我们就做完了！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e3+5,INF=1e9;
ll dp[N][N];//表示以i为根往下找j个叶子节点的最大值
ll siz[N],mon[N],idx[N];//子树大小和花费的钱，还有dfs序之后的下标
struct node{ll next,to;
}edge[N];
ll head[N],cnt;
ll n,m,k,x,y,tot;void add(ll from,ll to){edge[++cnt].next=head[from];edge[cnt].to=to;head[from]=cnt;return ;
}
void dfs(ll x){siz[x]=1;for(int i=head[x];i;i=edge[i].next){ll to=edge[i].to;dfs(to);siz[x]+=siz[to];}idx[++tot]=x;return ;
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n-m;i++){cin>>k;for(int j=1;j<=k;j++){cin>>x>>y;//要花钱就减mon[x]=-y;add(i,x);}}for(int i=n-m+1;i<=n;i++){//有收入就加cin>>x;mon[i]+=x;}dfs(1);//进行dfs序for(int i=0;i<=tot;i++)for(int j=1;j<=m;j++)dp[i][j]=-INF;for(int i=1;i<=tot;i++){x=idx[i];for(int j=1;j<=m;j++){if(n-m+1<=x) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+mon[x]);//如果是叶子节点else dp[i][j]=max(dp[i-1][j]+mon[x],dp[i-siz[x]][j]);//如果不是叶子节点}}for(int i=m;i>=0;i--) if(dp[tot][i]>=0) {cout<<i;return 0;}return 0;
}

P2515 [HAOI2010] 软件安装

题目简述

现在我们的手头有 $N$ 个软件，对于一个软件 $i$，它要占用 $W_i$ 的磁盘空间，它的价值为 $V_i$。我们希望从中选择一些软件安装到一台磁盘容量为 $M$ 计算机上，使得这些软件的价值尽可能大（即 $V_i$ 的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件 $j$ （包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 $0$。

我们现在知道了软件之间的依赖关系：软件i依赖软件$D_i$。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则$D_i=0$，这时只要这个软件安装了，它就能正常工作。

思路

嗯对这道题其实就是P2014 [CTSC1997] 选课
的升级版。

为什么说是升级版呢？因为这个图可能存在环，所以我们要干嘛？缩点！当然这里我没用 tarjan 缩点，用的是拓扑。

那么所以点完了之后存一个新图，当然缩点之后要建立虚拟源点，这里我们用 $dot[i]$ 来缩点，处理依赖环。

我们设 $now$ 为环上一点，则当缩点的时候需要将 $dot[now]$ 赋值为 $cnt$，这里的 $cnt$ 的作用为虚拟源点的下标。

好了，最后我们只需要改一改P2014 [CTSC1997] 选课的代码，也就是：

inline void dfsII(ll x){for(int i=0;i<=m;i++) dp[x][i]= (i>=w[x]) ? v[x]:-INF; for(int i=0;i<NG[x].size();i++){ll to=NG[x][i];dfsII(to);for(int j=m;j>=w[x];j--)//当前剩余的磁盘空间for(int k=w[to];k<=j;k++)//分配给子节点 to的磁盘空间dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[to][k]);}return ;
}

然后就可以写出全部的代码啦：

#include<bits/stdc++.h>
#define ll int
using namespace std;
namespace IO{const int maxn = (1 << 20);char buf[maxn], *p1 = buf, *p2 = buf;inline char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, maxn, stdin), p1 == p2) ? EOF : *p1++;}inline int read() {int f = 1, k = 0;char c = gc();while (!isdigit(c)) {if (c == '-') f = -1;c = gc();}while (isdigit(c)) {k = k * 10 + (c ^ 48);c = gc();}return f * k;}
}
using namespace IO;
const int N=505,M=110,INF=1e9;
vector<ll> G[M];
vector<ll> NG[M];
ll dp[M][N];
ll w[M],v[M],ind[M],dot[M],fa[M];
bool vis[M];
ll n,m,cnt;inline void dfsI(ll x){vis[x]=1;for(int i=0;i<G[x].size();i++){ll to=G[x][i];if(vis[to]) continue;ind[to]--;if(!ind[to]) dfsI(to);}return ;
}inline void dfsII(ll x){for(int i=0;i<=m;i++) dp[x][i]= (i>=w[x]) ? v[x]:-INF; for(int i=0;i<NG[x].size();i++){ll to=NG[x][i];dfsII(to);for(int j=m;j>=w[x];j--)//当前剩余的磁盘空间for(int k=w[to];k<=j;k++)//分配给子节点 to的磁盘空间dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[to][k]);}return ;
}
signed main(){n=read();m=read();cnt=n;for(int i=1;i<=n;i++) w[i]=read();for(int i=1;i<=n;i++) v[i]=read();for(int i=1;i<=n;i++){fa[i]=read();dot[i]=i;ind[fa[i]]++;G[i].emplace_back(fa[i]);}for(int i=1;i<=n;i++) if(!ind[i] && !vis[i]) dfsI(i);//拓扑for(int i=1;i<=n;i++){//缩点if(vis[i]) continue;cnt++;NG[0].emplace_back(cnt);ll now=i;while(!vis[now]){dot[now]=cnt;vis[now]=1;w[cnt]+=w[now];v[cnt]+=v[now];now=fa[now];}}for(int i=1;i<=n;i++)if(dot[i]==i)//如果没有被缩点就直接成为父亲节点的子节点NG[dot[fa[i]]].emplace_back(i);dfsII(0);cout<<dp[0][m];return 0;
}

树形DP

P2279 [HNOI2003] 消防局的设立

题目简述

有一颗 $n$ 个节点的树，一个消防站可以扑灭与它距离不超过 $2$ 的节点的火灾，则至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。

思路

这道题就是P2458 [SDOI2006] 保安站岗 的升级版。就是将距离为 $1$ 扩展到了 $2$。

但是这可不一样！现在我们要设 $5$ 种状态了！

dp[x][0] 表示覆盖到节点 $x$ 的爷爷节点和自己子树的最小放置个数。

dp[x][1] 表示覆盖到节点 $x$ 的父亲节点和自己子树的最小放置个数。

dp[x][2] 表示覆盖到节点 $x$ 和自己子树的最小放置个数。

dp[x][3] 表示覆盖到节点 $x$ 的儿子节点和其子树的最小放置个数。

dp[x][4] 表示覆盖到节点 $x$ 的孙子节点和其子树的最小放置个数。

嗯对大概就是很多状态，现在让我们来看看到底怎么转移。（注意：接下来的节点 $y$ 和 $z$ 均为节点 $x$ 的子节点，建议画一棵树更好理解）

首先对于 dp[x][0] 来说，如果要覆盖到爷爷节点那么一定要选 $x$，而对于 $y$ 来说则贪心选 dp[y][4]：

$$dp[x][0] = 1 + \sum dp[y][4]$$

其次是 dp[x][1]，对于 $x$ 的子树种来说，一定有一个节点既覆盖到 $x$ 的父亲节点又覆盖到它的兄弟节点，所以其他的儿子们只要覆盖到自己的儿子即可：

$$dp[x][1] = \min(dp[y][0] + \sum(y != z)dp[z][3])$$

然后是 dp[x][2]，覆盖到自己的话同理，有一个儿子覆盖到父亲节点，但无法覆盖到 $y$ 的兄弟节点，所以其他儿子要覆盖到自己即可：

$$dp[x][2] = \min(dp[y][1] + \sum(y != z)dp[z][2])$$

对于 dp[x][3] 的话，只要让每个儿子都覆盖到自己就好：

$$dp[x][3] = \sum dp[y][2]$$

dp[x][3] 同理，只要让每个孩子都覆盖到自己的儿子就好：
$$dp[x][4] = \sum dp[y][3]$$

现在分析完了，但是还有一步，因为可以发现 $dp[x][i]$ 应该包含 $dp[x][i+1]$，所以当 $dp[x][i]$ 比 $dp[x][i+1]$ 更优的话就应该更新一下。

好了我们终于做完了！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace OI{template<typename T> inline void read(T &x) {x = 0; T k = 1; char in = getchar();while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }while (isdigit(in)) x = x * 10 + in - '0', in = getchar();x *= k;}
}
using namespace OI;
const int N=1e3+5;
const int INF=1e9;
struct node{ll next,to;
}edge[N<<1];
ll head[N],cnt;
ll dp[N][5];//5种状态
ll n,x;void add(ll from,ll to){edge[++cnt].next=head[from];edge[cnt].to=to;head[from]=cnt;return ;
}
void dfs(ll now,ll fa){ll sumII=0,sumIII=0,tot=0;//sum记录fa[y][2] & fa[y][3] 的总和，tot记录儿子个数for(int i=head[now];i;i=edge[i].next){ll y=edge[i].to;if(y==fa) continue;dfs(y,now);sumII+=dp[y][2];sumIII+=dp[y][3];tot++;}if(!tot){//特判没有儿子dp[now][0]=dp[now][1]=dp[now][2]=1;dp[now][3]=dp[now][4]=0;return ;}dp[now][0]=1;for(int i=head[now];i;i=edge[i].next){ll y=edge[i].to;if(y==fa) continue;dp[now][0]+=dp[y][4];}dp[now][1]=dp[now][2]=INF;for(int i=head[now];i;i=edge[i].next){ll y=edge[i].to;if(y==fa) continue;dp[now][1]=min(dp[now][1],dp[y][0]+sumIII-dp[y][3]);dp[now][2]=min(dp[now][2],dp[y][1]+sumII-dp[y][2]);}dp[now][3]=sumII;dp[now][4]=sumIII;for(int i=1;i<5;i++) dp[now][i]=min(dp[now][i],dp[now][i-1]); //检查最小值return ;
}
int main(){read(n);for(int i=2;i<=n;i++){read(x);add(i,x);add(x,i);}dfs(1,0);cout<<dp[1][2];//即最小放置个数return 0;
}