博主鉴于自己的树形 dp 水平太 low 前段时间专门练习了下树形 dp。
就把题解和方法整理在一篇博客里算了。
希望自己以后遇到树形 dp 的题目能有更多准确的想法吧 🌹。

Type 1 普通树形 DP/普通树形背包

普通的树形 DP 就是由自己子节点的节点状态直接推到自己的节点状态。
所以做这种题首先需要抓住每个点的可能的节点状态，然后认真考虑各个节点状态之间的转移。
总结下重点：首先抓状态，状态一定不能漏；然后考虑状态之间的转移，争取不重不漏。
注意这里之所以说「节点状态」而非「状态」，是为了区分 DP 中的状态数组。「节点状态」是节点自身的状态。

普通树形背包就是通过背包合并子节点的状态得到当前点状态。
做这种题注意点实现技巧：刷表法/卡上下界优化至 $\mathcal{O}(n^2)$ /初始状态是设 f[0]=1 还是 f[1]=1 /是否需要在最后加上辅助转移的 f[0] = 1 等等。

大部分题目都是在有「节点状态」的情况下需要背包合并，细节比较多。码之前一定要想清楚转移。

T1 [HNOI2013] 消防局的设立

Description

太长了挂个链接算惹

Solution

根据上述所说，我们先来考虑节点的可能节点状态。假设在考虑子树 $p$ 。
首先 $p$ 可以被覆盖，也可以不一定被覆盖。如果被覆盖，$p$ 可以是被至少一个子节点覆盖，也可以是被至少一个孙子覆盖，也可以是选了自己；如果不一定被覆盖，那么 $p$ 只能被子树外的覆盖。被子树外的覆盖可能是父节点，也可能是爷爷/兄弟节点，这两种情况的区别在于：如果是爷爷/兄弟，那么 $p$ 的子节点一定已经全部被覆盖；如果是父节点，那么 $p$ 的孙子节点一定已经全部被覆盖。
由上可以看出总共有 $5$ 种情况，可能情况之间有交集，但一定不漏。
设 f[p][i] 表示 $p$ 节点对应的是 $i$ 状态，分类讨论转移即可。

T2 CF581F Zublicanes and Mumocrates

Description

给一棵 $n$ 个点的树，可以给每个点染黑白色，要求叶子节点黑白各一半。求最少的两端颜色不同的边的边数。
$1\leq n\leq 5\times 10^3$

Solution

「节点状态」自然就是 $0/1$ 代表白/黑。
所以可以设 f[p][i][0/1] 表示 $p$ 子树内，有 $i$ 个黑色叶子，最少的两端颜色不同的边的数量。分类讨论转移即可，复杂度可以通过卡上界优化到 $\mathcal{O}(n^2)$ 。

T3 [JSOI2018]潜入行动

Description

太长了挂个链接算惹

Solution

根据之前的方法，我们来找找「节点状态」。
考虑每个节点只有四种（2×2）状态：是否被覆盖、是否被选择。
为了代码的方便，我们可以用一个 $0\sim 3$ 的数字来代表「节点状态」

所以可以设 f[p][i][j] 表示 $p$ 子树内，选择 $i$ 个点，$p$ 的状态是 $j$ 的方案数。
然后用背包合并的方法就可以转移。
具体的转移比较繁琐但较简单，就不赘述了。

T4 [JLOI2015] 战争调度

Description

太长了挂个链接算惹

Solution

看上去似乎很套路：「节点状态」就是后勤/战争，然后背包合并一下。
实际上并不是。这个题最巨的一点在于：不同的叶子选择战争对于相同的战争父节点贡献不同。
意思是说：状态中只有记录了每个叶子的选择情况才可以转移。而这样状态数高达 $2^{512}$ ，肯定不行。
事实上，当一个叶子的所有祖先节点确定派别时，这个叶子确定派别后的贡献是确定的。而枚举一条链上的祖先的复杂度只有 $2^{n-1}$ ，叶子节点又只有 $2^{n-1}$ 个，所以从复杂度上来说这是可行的。
于是，我们可以先枚举叶子的祖先节点选择的派别，然后再背包合并。
设 f[p][i] 表示在 $p$ 的子树内选择 $i$ 个战争叶子点的最大贡献，逐层向上合并就行了。
复杂度 $\mathcal{O}(4^n)$ 。

这个题最高明的地方在于：平常树形 DP 算贡献都是在当前节点处（根据子节点和自身的状态）计算，而本题必须在叶子节点处计算，因为无法记录叶子结点的状态。希望自己能多领会这个方法。

Type 2 树形依赖背包 DP

树形依赖背包 DP 是树形背包的变种。
「依赖」的意思就是父节点是否选择影响了子节点是否选择。

T1 选课

Description

太长了懒得打惹

Solution

$\mathcal{O}(n\times V^2)$ 的做法在 $\text{Type 1}$ 中已经介绍了，简单的树形背包合并即可。
有两种优化至 $\mathcal{O}(n\times V)$ 的方法。这里只介绍一种比较好理解的。
在进入子树的时候，我们把当前节点的 DP 值赋值下去且强制把它儿子选了，最后遍历一遍出来后，这个子树的 DP 值就是选择了这个儿子的 DP 值，那么还有一种情况就是不选即原 DP 数组，所以最后两个 DP 数组取 $\max$ 即可。

Type 3 换根 DP

有一类题，它要求你求出对于所有点为根时的某个问题的答案。
还有一类题，虽说是无根树，但是当根确定时可以简化问题。
换根 DP 就在这两类题目的呼唤下应运而生。
换根 DP 的重点在于判断方程能否换根。有的方程就可换根性而言没有那么直观，需要转化 $\rightarrow$ Link 。换根 DP 在处理最大/次大/次次大等等问题时，应该着重考虑初值设置问题：是 $0$ 还是 $\pm\infin$ 。
换根 DP 十分灵活，做题时如果碰到瓶颈可以往这上面考虑。

T1 [COCI2014]Kamp

Description

挂个链接是真的香

Solution

设 f[p] 表示把 $p$ 子树内的人都送回家的最小代价。
考虑转移时可以发现：有的时候进入一棵子树后并不要求回来，但有时候要求回到子树根节点。所以再加一维表示是否回来。
转移可以这么考虑：

$f_{p,0}\leftarrow \sum f_{u,1} - \max\{f_{u,1}-f_{u,0}\}\\ f_{p,1}\leftarrow \sum f_{u,1}$

然后直接换根就行了。要求 $\max$ 的我们就再记个次大值。

T2 [APIO2014]连珠线

Description

题面好长实在懒得写

Solution

乍一看实在是没甚么头绪，只能得出蓝线肯定是个三点链。但这个三点链似乎怎么放都合法。

实际上，如果我们注意到这样一个性质，题目会好做很多：

当钦定一个点为开始节点时，三点链一定是祖先-儿子关系的链。

有了这个性质题目就方便多了。

对于每一条蓝边，我们考虑在深度较小的端点处计入贡献。这样三点链求贡献有一个经典的方法：设 f[p][0/1] 表示在 $p$ 的子树内， $p$ 是否是链中点的最大贡献。
第一维好理解，第二维看似突兀，实际上有依可循。三点链的贡献计算方式确定了，那么当 $0\rightarrow 1$ 和 $1\rightarrow 0$ 时，就一定要分别在右侧计入贡献。状态转移时计入的额外贡献是很清晰的。
考虑转移方程：

$g_u =\max\{f_{u,1}+\text{val}_{\text{fa}_u\rightarrow u},f_{u,0}\}\\ f_{p,0}\leftarrow \sum g_u\\ f_{p,1}\leftarrow (\sum g_u) + \max\{f_{u,0}+\text{val}_{\text{fa}_u\rightarrow u}-g_u\}$

换根的时候不要急，理清思路一条一条换就行了。

Type 4 杂题

DP 本就是灵活的东西。上树后也不例外。
总是不可能将列出一个所有的表，将所有的 DP 都列进来呢。
那就把做过的一些好题放在杂题里吧。

T1 [IOI2015]河流

Description

太长了挂个链接算惹

Solution

真的是苦思很久不会做。
对于这种「当前节点并不能确定子树贡献」的题目，可能的方法我之前只会「费用提前计算」。
但在这里似乎也不能提前计算，因为 $\sum w$ 还是蛮大的，转移时还要背包合并，时空复杂度均太高。
我们从贡献的计算方式出发考虑状态 。显然， $p$ 节点及其子树内节点一定是在 $p$ 或者 $p$ 的某个祖先节点处计算贡献。所以，设计状态为 f[p][i][j] 表示 $p$ 子树内用了 $i$ 个伐木场，$p$ 的最近祖先在 $j$ 时的最小贡献。
仅此还不方便转移。因为第二维为 $0$ 和第三维为 $p$ 冲突了。我们干脆设 g[p][i][j] 表示选择了 $i$ 做伐木场，f[p][i][j] 表示未选择 $i$ ，就可以了。
复杂度应该是 $\mathcal{O}(n^3)$ 的吧。

T2 [POI2013]Triumphal arch

Description

太长了挂个链接算惹

Solution

有一个显然的性质：对于聪明的 B 来说，它一定不会走回头路。走回头路意味着必输。
一开始肯定都会往度数上考虑：设 f[p][i] 表示 B 在点 $p$ 时，向下走 $i$ 步的最大总度数。大概是如下转移

$f[p][i] \leftarrow \max(f[u][i-1]) +\text{deg}_p - [p\not =\text{root}]$

可以用长链剖分优化一下求解过程，最后在对于 $\forall i\in[1,n]$ ，求出 $\lceil\frac{f[1][i]}{i}\rceil$ 的最大值当作答案。

看上去有理，事实上这样子做是不行的。简单来说就是取 $f[1][i]$ 和 $f[1][j]$ 的位置可能不一样，所以在之前的步骤中需要染几个多余的颜色来保证 B 一定走到 $i$ 而不是 $j$ 。染的那几个多余的颜色是没办法计入到 $f[1][i]$ 中的，所以这条路走不通。

换一个思路，可以发现答案一定具有可二分性。我们二分答案 $k$ ，问题转化为可行性判断。
可行性就好做多了。设 f[p] 表示在当前的 $k$ 下，若 B 在 $p$ 处，至少需要借助多少子树外的力量才可以保证 A 赢。设 cnt[p] 表示 $p$ 的子节点个数，转移有

$f_p\leftarrow\max\{0,\sum f_u+k-\text{cnt}_p\}$

问题解决了！复杂度 $\mathcal{O}(n\log_2n)$ 。

T3 CF1153D Serval and Rooted Tree

Description

不长但挂个链接算惹

Solution

这种给点标号的题目可以想到类似于「分治」的做法。
就是先对于若干个区间，求出区间中的数相对大小关系是什么时的最优解，再把这些区间拼起来得到更大的区间的相对大小关系时的最优解。

比如说这题，设 f[p] 表示节点 $p$ 可能的最大值， sz[p] 表示 $p$ 子树内的叶子节点个数。
假如第 $p$ 个点的操作是 $\max$ 。对于 $p$ 的某个子节点 $u$ ，它代表的区间是 $1\sim \text{sz}_u$ 。我们若钦定 $p$ 最后的最大值是由 $u$ 继承来的，那么 $u$ 代表的区间一定是在 $p$ 代表的大区间中排在最后面。此时的转移为

$f_p \leftarrow \max\{f_u + \text{sz}_p-\text{sz}_u\}$

否则第 $p$ 个点的操作是 $\min$ 。对于 $p$ 的两个子节点 $u$ 和 $v$ ，我们钦定 $u$ 在最后继承给 $p$ （也就是值比 $v$ 小），那么 $u$ 可能的最大值就是 $f_u+f_v-1$ 。因为相当于把 $1\sim f_v-1$ 放在大区间最前面，$1\sim \text{sz}_u$ 紧随其后，$f_v\sim \text{sz}_v$ 放在最后，那么这时是在 $u$ 最终值小于 $v$ 的情况下最大化了 $u$ 的值。观察到最后的答案形式为 $f_u+f_v-1$ ，也就是说我们钦定 $v$ 小答案也是一样的。所以转移为

$f_p\leftarrow (\sum f_u-1) +1$

复杂度 $\mathcal{O}(n)$ 。