|
通常，我们从根节点出发，向子节点做深度优先搜索，并由其子节点的最优解合并得到该节点的最优解。有些问题，我们还需再次从根节点出发，向子节点做深度优先搜索，对于树上的每个节点（除根节点外），由父节点的信息（父节点合并后的信息，除去该孩子的信息，就是其与孩子的信息）更新该节点的信息
一、树上动态规划
例题1
给出一个n个节点的树，找出一个节点为根，使得树上所有节点的深度之和最大
我们先假设1号节点就是根节点，这时候，我们对树做一次dfs就可以求出每个点的子树的大小，并且同时也可以求出所有节点的深度之和
这时候，如果我们把根节点转移到1号节点的一个儿子x上，那么x节点对应的所有以1为根节点的子树中的节点的深度都要减去1，而除了x以外的其他儿子节点和1节点的深度都要增加1，所以对应总的深度和就可以计算出来，也就是说通过父节点信息我们可以推算出子节点的信息，这样我们就可以在树上进行动态规划了
size[x]：整棵树以1为根节点时，以x为根的子树的节点数量
f[x]:整棵树以1为根节点时，以x为根的子树的所有节点的深度之和
ans[x]：整棵树以x为根时所有节点的深度之和
算法流程：dfs一遍，由子节点信息得到size[x],f[x]；再dfs一遍，由父节点信息得到ans[x]，求出最大值? ? O(N)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,u,v,cnt,head[2000005],maxn,xid;
ll ans[2000005],f[2000005],size[2000005];
struct node{
int to,nxt;
}e[2000005];
void insert(int u,int v){
e[++cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(int u,int fa){
f[u]=0;
size[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
size[u]+=size[v];
f[u]+=f[v]+size[v];
}
}
void dp(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
ans[v]=ans[u]+n-2*size[v];
dp(v,u);
}
}
int main(){
cin >> n;
for(int i=1;i<=n-1;i++){
cin >> u >> v;
insert(u,v);insert(v,u);
}
dfs(1,0);
ans[1]=f[1];
dp(1,0);
for(int i=1;i<=n;i++){
if(ans[i]>maxn){
maxn=ans[i];
xid=i;
}
}
cout << xid << endl;
return 0;
}
练习1：洛谷p1352没有上司的舞会https://www.luogu.com.cn/problem/P1352
#include <bits/stdc++.h>
using namespace std;
int a[60005],dp[60005][2],head[60005],cnt,n,ru[60005],root;
struct node{
int to,nxt;
}e[60005];
void insert(int u,int v){
e[++cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(int u){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dfs(v);
dp[u][0]+=max(dp[v][0],dp[v][1]);
dp[u][1]+=dp[v][0];
}
dp[u][1]+=a[u];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n-1;i++){
int u,v;
cin >> v >> u;
ru[v]++;
insert(u,v);
}
for(int i=1;i<=n;i++){
if(ru[i]==0)root=i;
}
dfs(root);
cout << max(dp[root][0],dp[root][1]) << endl;
return 0;
}
二、树上01背包问题
前面我们接触的树形dp状态都是一维的，每个点只需要一个值记录状态信息就足够了。下面我们学习每个点需要多个状态的树形dp
例题2
给出一棵有n个点的有根树，根节点的编号为1，初始的时候，树上所有边都没有被打通，而打通每一条边都需要一定的能量。每个点都只有m点能量，并且只能用来打通其和儿子之间的边，求最多有多少个点和根节点联通
dp[i]：表示以i为根节点的子树最多能有多少个和i联通，那么可以把u的每个子节点v都看成一个物品，花费是打通<u,v>这条边的花费，而价值就是dp[v]，所以求解每个点的dp值就成了一个01背包问题
void dfs(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
}
memset(f,0,sizeof(f));
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
int cost=e[i].cost;
int val=dp[v];
if(v==fa)continue;
for(int j=m;j>=cost;j--){
f[j]=max(f[j],f[j-cost]+val);
}
}
dp[u]=f[m]+1;
}
三、树上多重背包问题
前置芝士：回顾一下多重背包的写法
最外层循环枚举物体，第二层循环枚举背包体积，第三层循环枚举选择的数量
for(int i=1;i<=n;i++){
for(int j=v;j>=0;j--){
for(int k=0;k<=n[i];k++){
if(j>=c[i]*k)dp[j]=max(dp[j],dp[j-c[i]*k]+w[i]*k);
}
}
}
树上的背包问题，大多数情况下都会是多重背包问题（完全背包），把树上的01背包的问题稍微改动一下，就变成多重背包问题。
我们把能量的花费变成全局的，而不是固定每个点的能量。
例题3：
给出一棵有n个点的有根树，根节点编号为1，初始的时候，树上的所有边都没有被打通，而打通每一条边都需要一定的能量，一共有m点能量，求最多有多少个点和根节点能联通。
分析：这时候，费用变成了全局，我们不知道最优情况下，每个点以及其子树分别花费了多少能量。所以利用动态规划的思想，用dp[u][x]表示在点u以及其子树一共花费了x点能量的时候最多的联通点数
对于u的一个子节点v，假设我们给u的能量花费为x，那么可以分给v以及其子树0、1、2……x-c<u,v>点能量，其中c<u,v>表示边<u,v>的花费
所以我们可以把v以及其子树看成一个物品，它有很多种选择，选择花费能量i对应的价值为dp[v][i]（这里的价值不是线性的，前面接触到的多重背包价值都是线性的）。这样，对于u套用多重背包的做法，就可以求出dp[u][0]、dp[u][1]……dp[u][m]
int dp[maxn][maxn];
void dfs(int u,int fa){
//先求出所有子节点的背包
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
}
//转移
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
int c=e[i].cost;//边的花费
if(v==fa)continue;
for(int j=m;j>=0;j--){//枚举背包容量
for(int k=c;k<=j;k++){//枚举子树v的花费
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k-c]);//背包容量为k-c
}
}
}
//每种状态的背包都要加一，u本身也要计数1
for(int i=0;i<=m;i++)dp[u][i]++;
}
练习2：
一棵有根树，每个点有一个花费，选择一个点的收益为其子树中点的个数，求收益至少为m的最少花费
dp[u][i]表示u的子树中选了i个点的最小花费
1，如果决定选择u，那么u的子树都直接选择是最优的，也就是dp[u][sz[u]]=c[u]
2.如果不选择u，那么就需要对u进行一次多重背包转移，这时候，u及其子树最多只可能选sz[u]-1个人
void dfs(int u){
sz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dfs(v);
sz[u]+=sz[v];
}
dp[u][0]=0;
dp[u][sz[u]]=c[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
for(int j=sz[u]-1;j>=0;j--){
for(int k=1;k<=j;k++){
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
}
}
经典树形dp习题汇总：
1.[HAOI2015]树上染色?https://www.luogu.com.cn/problem/P3177
有一棵点数为?n?的树，树边有边权。给你一个在 0～n?之内的正整数?k，要在这棵树中选择?k?个点，将其染成黑色，并将其他 的?n?k个点染成白色。将所有点染色后，会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。0≤n,k≤2000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int to,nxt,w;
}e[5005];
int cnt,head[5005],n,m,sz[5005];
ll f[2005][2005];
void insert(int u,int v,int w){
e[++cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
void dfs(int u,int fa){
sz[u]=1;f[u][0]=f[u][1]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);sz[u]+=sz[v];
for(int j=min(m,sz[u]);j>=0;j--){
if(f[u][j]!=-1)f[u][j]+=f[v][0]+1ll*sz[v]*(n-m-sz[v])*e[i].w;
for(int k=min(j,sz[v]);k>0;k--){
if(f[u][j-k]==-1)continue;
ll res=1ll*(k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k))*e[i].w;
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+res);
}
}
}
}
int main(){
//memset(head,-1,sizeof(head));
memset(f,-1,sizeof(f));
cin >> n >> m;
if(n-m<m)m=n-m;
for(int i=1;i<=n-1;i++){
int u,v,w;
cin >> u >> v >> w;
insert(u,v,w);insert(v,u,w);
}
dfs(1,0);
cout << f[1][m] << endl;
system("pause");
return 0;
}
2.有线电视网?https://www.luogu.com.cn/problem/P1273
某收费有线电视网转播一场比赛。转播网和用户终端构成一棵树状结构，这棵树的根结点位于比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。现在每个用户都准备了一笔费用想观看这场比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。请找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
#include <bits/stdc++.h>
using namespace std;
const int inf=0x7ffffff;
int n,m,head[5005],f[5005][5005],v[5005],cnt;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct node{
int to,nxt,w;
}e[2000005];
void insert(int u,int v,int w){
e[++cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
int dfs(int u,int fa){
f[u][0]=0;
if(u>n-m){
f[u][1]=v[u];return 1;
}
int sum=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
sum+=dfs(v,u);
for(int j=sum;j>0;j--){
for(int k=0;k<=j;k++){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-e[i].w);
}
}
}
return sum;
}
int main(){
n = read(), m = read() ;
int mm = n-m ;
for(int i=1;i<=mm;i++) {
int k = read() ;
for(int j=1;j<=k;j++) {
int x = read(), z = read() ;
insert(i,x,z) ;
insert(x,i,z) ;
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j] = -inf ;
for(int i=n-m+1;i<=n;i++) v[i] = read() ;
dfs(1,0) ;
for(int i=m;i>=0;i--) {
if(f[1][i] >= 0) {
printf("%d",i) ; return 0 ;
}
}
return 0;
}
|