树形 dp / 换根 dp 入门小记

标签：子树 int 转移 fa 换根节点 dp 小记

背景

4.14 打 abc 的时候一眼 e 题是换根模板，但是我不会，于是就来补档了。

什么是树形 dp / 换根 dp

一种在树上的 dp，一般用 dfs 进行状态转移。

树形 dp 一般用儿子来更新父亲的答案。

换根 dp 一般在第二次 dfs 时用父亲的答案转移到儿子去。

引入

经典树形 dp 例题：没有上司的舞会。

不难设计状态，\(dp_{i,0/1}\) 表示 \(i\) 这个人来不来，子树内的最大价值。

状态转移是简单的：

\[dp_{x,0}=\sum \max (dp_{i,1},dp_{i,0}) \]

\[dp_{x,1}=\sum dp_{i,0} \]

其中 \(i\) 是 \(x\) 的儿子。

经典树上背包例题：选课。

树上背包的时间复杂度证明 + 优化还是蛮麻烦的。所以我~~不求甚解~~不管了。我不会。

设 \(dp_{i,j,k}\) 代表在 \(i\) 子树内处理第 \(j\) 个儿子并选择了 \(k\) 个课程的最大价值。

转移有点麻烦，算是比较复杂的树形 dp：

\[dp_{x,j,k}=\max\limits_{l=0}^{k-1} dp_{x,j,k-l}+dp_{x,j-1,l} \]

然后你会发现这玩意不就是背包吗，把第二维给吃了，变成：

\[dp_{x,j}=\max\limits_{k=1}^{j-1} dp_{x,j-k}+dp_{i,k} \]

上面的变量有点乱，把第二维吃了以后 \(k\) 换成了 \(j\)，\(l\) 换成了 \(j\)。\(i\) 是 \(x\) 的儿子。

注意这题要选儿子的话父亲也要选，初始化是第 \(i\) 门课的学分就是 \(dp_{i,1}\)。

时间复杂度好像可以证明是 \(\mathcal O(nm)\) 的。

换根 dp 也称二次扫描。顾名思义，要 dfs \(2\) 次。

通过第一次 dfs 找到根节点的答案，然后再不断转移给儿子。

所以看到题目问对于所有节点求答案或者最大最小值就可以想想是不是换根了。

一般思考换根要考虑两个东西：根节点的答案如何计算、怎么将答案从父亲传向儿子。

经典换根 dp 例题：[POI2008]STA-Station。

第一次求出以 \(1\) 节点为根的深度之和是简单的，考虑第二次怎么转移。

不妨设现在已经知道了 \(x\) 节点的答案，现在要转移到 \(y\) 节点上。

然后手推一波可以发现，\(y\) 子树内所有的节点深度都减了 \(1\)，\(y\) 子树外所有节点的深度都加了 \(1\)。

所以转移方程：

\[dp_i=dp_x-s_i+(n-s_i) \]

上面的 \(s_i\) 是子树大小，可以在第一次简单地处理出来。

习题

dp 这种东西会了例题作用不大，主要还是要考做题积累经验。学会如何设计 dp 数组含义和动态转移方程。

提前声明一下：以下的 \(x\) 指当前的节点，\(i\) 为 \(x\) 的一个儿子。

ABC348E

没错，就是这题。这是一道 \(n\) 倍经验的经典老题了。

根节点答案的计算是容易的，考虑怎么转移。

不难发现 \(i\) 子树内所有的节点深度都少了 \(1\)，子树外的深度都多了 \(1\)。开个 \(s_x\) 表示 \(x\) 子树内点权和就好了。

转移方程：

\[dp_i=dp_i-s_i+(sum-s_i) \]

其中 \(sum\) 是所有的点权和。

P2015

也是一道树上背包经典题。

直接吃第二维罢，设计 \(dp_{x,j}\) 为留下 \(j\) 条树枝的最多苹果。

比较明显的背包：

\[dp_{x,j}=\max\limits_{k=0}^{j-1}dp_{x,j-k-1}+dp_{i,k}+v \]

~~这题甚至不用初始化。~~ 上面的 \(v\) 是枚举到这条树枝上的苹果数。注意是 \(dp_{x,j-k-1}\)，减一是因为有一条树枝要给到当前枚举的这个。

P1131

简述一手题面：给定根，每次操作可以使一条边的长度加一，问最少多少次操作可以使叶子结点的深度相同。

~~说实话我都感觉这题不能叫做 dp。~~

考虑贪心，显然最后的深度都是初始时的最大深度，不妨设为 \(ma\)。

设 \(s_x\) 为 \(x\) 子树内的最大深度。递归到 \(x\) 时在边上加上 \(ma-s_x\) 显然是最优的。注意递归是顺便将加上的标记下传了。

CF1187E

注意到第一次可以任意选点，大胆猜测是换根 dp。

然后好像甚至连根节点怎么计算答案都不知道？？？

手搓一波样例，把每次有贡献的点都加一。然后你会惊奇地发现每个点的贡献就是它的深度加一！

为什么呢？不妨把每次的起点都看成根，那么就会把树分成每一个子树，本次的贡献为子树大小。由于每个下一次能选择的节点都在不同的联通块，并且都是子树的根。

然后又是一次循环，到最后叶子节点时贡献为 \(1\) 。

不难发现一个节点能被选择当且仅当它的父亲已经被选完。并且父亲每选一次，该节点贡献加一。

理解完后答案很容易求，就是例题再加上 \(n\)。

P3177

~~好像有大佬在 hack \(\mathcal O(N^3)\) 的假做法，等出来 hack 数据之后再改。~~

按照这里优化了一手上下界，跑得真快。

~~草，还是错的，自己搞了一个 hack。~~

原来是交错代码了，现在对了。

好题。

一开始理所当然地想设计 \(dp_{x,j}\) 为在 \(x\) 子树内染了 \(j\) 个点的最大价值。然后想了好久都没有思路，因为还会与子树外的点产生贡献。

正确的设计方式应该是在 \(x\) 子树内染了 \(j\) 个点对答案的贡献。这样设计的好处是转移时直接求和即可，没有其他的贡献。

设计好数组就转移就很方便了：

\[dp_{x,j}=\max\limits_{k=\max(j-s_x+s_i,0)}^{\min(j,s_i)}dp_{x,j-k}+dp_{i,k}+v\times k\times (m-k)+v\times (s_i-k)\times (n-m-s_i+k) \]

上面的 \(k\) 是枚举在 \(i\) 子树内选多少个黑点，\(v\) 是边的权值，\(s_i\) 是 \(i\) 子树大小，\(s_x\) 是目前枚举到的 \(x\) 子树大小。\(k\times (m-k)\) 是两边的黑点连起来经过当前这条边的次数，因为在两边任意选一个点都会经过；同理，\((s_i-k)\times (n-m-s_i+k)\) 就是白点的。

注意转移的边界和一些细节。原始的大部分题解都是要把 dp 数组 memset 成 \(-1\)，不然会 WA。理由是可能会从不合法的状态转移而来，但这样也同时导致了时间复杂度是错误的。

为什么会从错误的状态转移而来呢？我们枚举了 \(i\) 子树内有 \(k\) 个点，那么就要要求前面的子树内至少有 \(j-k\) 个点。原本 \(k\) 从 \(0\) 开始枚举的话就会有可能前面点的个数不够，从而导致从不合法的状态转移来。

时间复杂度的分析建议看这个帖子，这里就不过多赘述了。简单地说，就是任意两个点只会在 lca 处合并一次，所以时间复杂度是 \(\mathcal O(n^2)\) 的。

本题的困难主要在需要打破以前只计算子树内答案的思维，直接考虑对答案的贡献，正确设计 dp 数组。

这里给出代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=2010;
int n,m,s[N];
long long dp[N][N];
vector<pair<int,int>>v[N];
void dfs(int x,int fa)
{
	s[x]=1,dp[x][0]=dp[x][1]=0;
	for(auto i:v[x])
	{
		if(i.fi==fa)continue;
		dfs(i.fi,x);
		s[x]+=s[i.fi];
		for(int j=max(m,s[x]);j>=0;j--)
			for(int k=max(j-s[x]+s[i.fi],0);k<=min(j,s[i.fi]);k++)//控制好上下界
				dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[i.fi][k]+1ll*k*(m-k)*i.se+1ll*(s[i.fi]-k)*(n-m-s[i.fi]+k)*i.se);
	}
}
int main()
{
	cin>>n>>m;
	m=min(m,n-m);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	dfs(1,0);
	cout<<dp[1][m];
	return 0;
}

P2279

这题要是 dp 的话是个大分讨，太麻烦了。~~所以在 dp 小记里来点不一样的。~~

考虑贪心。优先考虑深度最大的点，显然在它的爷爷设置最优。然后就没了。

代码实现还是蛮有难度的。

看了第一篇题解，是真的神。甚至不用跑图！

因为题目给图的方式是给出每个点的父亲，并且父亲的编号还小于自己。所以输入时就能把每个点的深度都给求出来了。

然后把每个点按深度排序。设 \(f_i\) 为最近的消防站的距离。

每次新建消防站时直接在父亲和爷爷节点加标记就好了，兄弟节点可以通过父亲和爷爷转移而来。

给个代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,ans;
int fa[N],de[N],id[N],f[N];
bool cmp(int a,int b)
{
	return de[a]>de[b];
} 
int main()
{
	cin>>n;
	id[1]=1,f[0]=f[1]=1e9;
	for(int i=2;i<=n;i++)
	{
		int x;
		cin>>x;
		fa[i]=x,id[i]=i;
		de[i]=de[x]+1;
		f[i]=1e9;
	}
	sort(id+1,id+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		int now=id[i],f1=fa[now],f2=fa[f1];
		f[now]=min(f[now],min(f[f1]+1,f[f2]+2));
		if(f[now]>2)
		{
			f[now]=2,ans++;
			f[f1]=min(f[f1],1),f[f2]=0;
			f[fa[f2]]=min(f[fa[f2]],1),f[fa[fa[f2]]]=min(f[fa[fa[f2]]],2);
		}
	}
	cout<<ans;
	return 0;
}

P2458

这是上面那题但是一个保安只能管理距离为 \(1\) 以内的点。

这样 dp 的话分讨就少点了，设计 \(dp_{x,0/1/2}\) 为：

在父亲放保安
在自己放保安
在儿子放保安

这题还是比较简单的。就不多赘述了。

注意第 \(3\) 种情况的转移：如果有儿子 第 \(2\) 种比第 \(3\) 种还小，那就直接取最小值就好了。不然还要枚举一遍哪个儿子放保安更优。

这里放一下第 \(3\) 种情况的转移（代码里的每种情况的编号都减了一）：

for(int i:v[x])
{
  if(i==fa)continue;
  sum+=min(dp[i][1],dp[i][2]);
  if(dp[i][1]<=dp[i][2])chk=1;
}
if(chk)dp[x][2]=sum;
else
{
  for(int i:v[x])
    if(i!=fa)dp[x][2]=min(dp[x][2],sum-dp[i][2]+dp[i][1]);
}

CF1324F

简单题。

对于每个点都要求出答案，所以考虑换根 dp。

显然将黑点的价值视为 \(-1\)，将白点的价值视为 \(1\)。

如果子树是负的那么当然不选，正的加入连通图中。

思考怎么转移，如果 \(i\) 子树是非正的，那么 \(i\) 与 \(x\) 不在一个连通块内。要么把 \(i\) 加进 \(x\) 的联通块内，要么就是 \(-1\)。取最大值即可。否则，那么 \(i\) 与 \(x\) 在一个联通块内。要么就是 \(x\) 的答案，要么就是本身子树的答案，因为 \(x\) 可能是 \(-1\)。

P1272

有难度的树上背包。

考虑先不吃第二维。定义 \(dp_{x,l,j}\) 为处理 \(x\) 的第 \(l\) 个儿子时取 \(j\) 个节点的最小花费。

可以写出这样的转移方程：

\[dp_{x,l,j}=\min(dp_{x,l-1,j}+1,dp_{x,l-1,j-k}+dp_{i,s_i,k}) \]

上面的 \(s_i\) 是 \(i\) 的儿子个数，\(k\) 是枚举在 \(i\) 儿子选多少个点。

后面那一项应该还是蛮好理解的。对于前面那项，加一是因为如果不在 \(i\) 子树内选点的话，要把 \(x\to i\) 的这条边断开才行。

然后按常规把第二维吃了就好了，注意转移方程前面那项加一。

做完这题，要对方程的转移有更深刻的理解。或许一开始思考不应该直接滚动数组，而是明确了方程之后再滚动。转移也或许并不是一昧地求 \(\max\) 和 \(\min\)，可能还有额外的贡献。