浅谈树形DP

简介

树形 $dp$ 是一类很容易看出来的 $dp$，但是写起来却有很多的细节和技巧

一道树形DP需要注意的各种地方

DP方程的定义及初始化

树形 $dp$ 中，$dp$ 方程的定义非常重要，且一道树形 $dp$ 题往往有很多种不同的 $dp$ 的定义

要注意如果当前的 $dp$ 方程不能涵盖所有情况或者出现某些情况被包含多次一定及时修改

树形 $dp$ 很可能一个字的差异会造成巨大的区别

树形 $dp$ 的初始化同样是一个令人头大的问题，因为大部分情况下初始化都不太符合方程的定义，且叶子节点和其它节点的初始化也总是不尽相同，而且只能具体题目具体分析

DP方程的转移

树形 $dp$ 中的转移大部分可以分为两类，一类是累加转移，剩下一类是展开转移

累加转移的意思就是在用 $f[v]$ 更新 $f[u]$ 时，$f[u]$ 已经包含了其它的 $f[v]$ 的值了，可以说大部分树形 $dp$ 都是累加转移

展开转移不太常见，例如经典的一个问题是求有多少点集，点集中不存在有祖先关系的节点，这里的 $f[u]=\prod (f[v]+1)$

这里使用展开转移显然更好理解

累加转移

需要注意的是，从某种意义上正是累加转移的方式导致了树形 $dp$ 的方程初始化稍微有一点奇怪

另外一点，当我们有多个 $dp$ 方程时，累加转移可能会对多个转移方程转移的顺序有要求

CF 1146F Leaf Partition

简要题意：给定一棵以 $1$ 为根的有根树，设 $L$ 为一个叶子节点的集合，$f(L)$ 就是这些叶子节点的最小连通子图，现在要求将所有叶子节点划分成若干个集合，使得任意两个叶子结合 $S$ 和 $T$ 满足 $f(S)\cap f(T)=\empty$，求方案数 $998244353$ 取模

$n\le 2\times 10^5$

简要题解：我们定义 $f[u]$ 表示 $u$ 向下直连一棵染色的子树，注意 $u$ 本身不属于这棵被染色的子树

$g[u]$ 表示 $u$ 是一棵染色的子树的根，$h[u]$ 表示 $u$ 没有被染色

1
2
3

g[u] = (g[u] * (f[v] + 2 * g[v] + h[v]) + f[u] * (f[v] + g[v])) % p;
f[u] = (f[u] * (h[v] + g[v]) + h[u] * (f[v] + g[v])) % p;
h[u] = h[u] * (h[v] + g[v]) % p;

展开转移

展开转移在 $f[u]$ 直接等于某种形式的 $f[v]$ 时比较好用

CF 1223E Paint the Tree

简要题意：给定一棵有 $n$ 个点的无根树和 $k$，每个点要染上恰好 $k$ 种颜色，现在有无数种颜色，每种颜色最多用两次，当一条边的两个端点附上的颜色中有至少一种相同颜色时，这条边的贡献就是这条边的权值，否则是 $0$，求一种染色方案，使得这棵树的所有边的贡献之和最大

简要题解：题目可以转化为在树上选取若干条边，需要保证加入这些边后没有一个点的度超过 $k$，问最大边权和

对于儿子，我们只需要知道儿子还能不能选一次，所以我们令 $f[u]$ 表示还能选，$g[u]$ 表示不能选

在转移的时候，我们首先都选 $g[v]$，然后将 $f[v]+w-g[v]$ 排序选前 $k$ 个作为 $g[u]$，前 $k-1$ 个作为 $f[u]$

树形DP的空间优化

自下而上，空间复杂度 $O(maxdep\times S)$，其中 $maxdep$ 表示树的最深节点的深度
自上而下，空间复杂度 $O(\log n\times S)$，这个 $\log n$ 是指轻边的个数，我们树剖后，先向轻儿子转移，最后向重儿子转移
1. 简要题意：现在有 $n$ 个操作，每个操作要么在最右边添加一堆石子，个数为 $a$，价值为 $b$，要么删除最右边的一堆，在每次操作后，求价值最小的移除方案使得先手必败
  
  $n\le 4\times 10^4,a<2^{14}$，空间限制 $8M$
  
  简要题解：首先我们不考虑空间限制，容易得到操作构成一个树形结构，每次相当于查询从点 $u$ 的树链上选价值和最小的若干个点使得它们的以后和等于 $u$ 的树链的异或和
  
  容易得到一个 $dp$，令 $f[u][S]$ 表示从 $u$ 到根，异或和为 $S$ 的最小价值，我们考虑压缩一下第一维
  
  实际上第一位我们并不用存 $1$ 到 $n$，我们只需要保证从 $u$ 点到其子树内第一维不会重复即可
  
  我们考虑轻重链剖分，然后令第一维表示轻边的个数，那么第一维就不会超过 $O(\log n)$，然后我们先 $dfs$ 轻儿子，最后 $dfs$ 重儿子即可
  
  时间复杂度 $O(nS)$，空间复杂度 $O(S\log n)$
  
  The 2020 ICPC Asia Macau Regional Contest I Nim Cheater

树形背包

树形背包时间复杂度

$O(n^2)$

证明：任意两个点只会在 $lca$ 处有 $1$ 的贡献

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u);
        for (int S = 0; S <= sz[u]; ++S)
            for (int T = 0; T <= sz[v]; ++T) ...
        sz[u] += sz[v];
    }
}

$O(nk)$

证明：容易想到，我们只需要考虑所有兄弟节点对的贡献

如果两个兄弟节点的子树大小都大于等于 $k$，那么他们合并一次的贡献是 $O(k^2)$ 的，但是他们合并之后会使待合并的大小减少 $k$，所以像这样的合并只会出现 $O(\frac n k )$ 次

如果一个节点的子树大小大于等于 $k$，另一个节点的子树大小小于 $k$，不妨令其为 $t$，那么他们合并一次的贡献是 $O(tk)$ 的，但是他们合并之后会使待合并的大小减少 $t$，所以像这样的合并的总复杂度只有 $O(nk)$

如果两个兄弟节点的子树大小都小于 $k$，我们对于每个点单独考虑他们这样合并的贡献，显然一个点对这样合并的总贡献是 $O(k)$ 的，而总点数是 $O(n)$，那么这样的合并的复杂度就是 $O(nk)$

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u);
        for (int S = 0; S <= min(k, sz[u]); ++S)
            for (int T = 0; T <= min(k, sz[v]); ++T) ...
        sz[u] += sz[v];
    }
}

例题

简要题意：给定一棵 $n$ 个点的无根树，现在有 $k$ 个监听装置，每个节点至多安放一个监听装置，一个安放了监听装置的节点可以监听相邻的节点，但不能监听自己，求恰好使用 $k$ 个监听装置且每个节点都至少被一个节点监听的方案数

$n\le 10^5,k\le 100$

简要题解：我们令 $f[u][S][0/1][0/1]$ 表示 $u$ 的子树内一共使用了 $S$ 个监听装置，$u$ 点是否使用监听装置，$u$ 点是否被监听到，时间复杂度 $O(nk)$

Luogu P4516 [JSOI2018]潜入行动
简要题意：给定一棵 $n$ 个点的树，每个点有一个颜色 $c_i$，求有多少连通块满足存在某种颜色的出现次数大于其它所有颜色的出现次数的和

$n\le 3000$

简要题解：我们首先考虑枚举颜色，把是这个颜色点赋值成 $1$，不是变成 $-1$，那么我们跑一个树形背包，容易发现大于 $0$ 的都是合法的

这样时间复杂度看起来是 $O(n^3)$ 的，但注意到如果我令当前枚举的颜色为 $c$，该颜色的总数为 $k_c$，那么如果背包的大小下雨 $-k_c$ 是没有意义的，所以我们可以把背包总容量限制为 $[-k_c,k_c]$，那么这样做一次的复杂度就是 $O(nk_c)$，所以总的时间复杂度为 $O(n\sum k_c=n^2)$

2021 ICPC Southeastern Europe Regional Contest C Werewolves
简要题意：给定一个 $n$ 个点无向树，求对于 $k\in[1,n - 1]$，有多少棵这 $n$ 个点的完全无向图的生成树与这棵树有恰好 $k$ 条边重复

$n\le 100$

简要题解：第一种做法是比较直观无脑的，我们考虑将问题稍做转换，如果我们只选择 $k$ 条边，那么相当于现在还有 $n-k$ 个连通块，我们知道一个结论是，使用 $k-1$ 条边将 $k$ 个连通块连通的方案数为 $n^{k-2}\prod_{i=1}^ks_i$，其中 $s_i$ 表示第 $i$ 个连通块的大小

根据这个结论，我们考虑用树形 $dp$ 求出选择 $k$ 条边的 $\prod_{i=1}^k s_i$ 的和，连通块的大小的乘积这个东西有一个经典的做法就是我们记录每个连通块选恰好一个点的方案数，我们令 $f_{u,i,0/1}$ 表示连通块有 $i$ 个，$u$ 所在的连通块是否有选点，我们求出这东西之后将其乘上 $n^{k-2}$ 得到的东西并不是答案，这个可能会算重，我们再容斥一下即可，时间复杂度 $O(n^2)$

CF 917D Stranger Trees
简要题意：给定一棵 $n$ 个点的无根树，每个点有一个物品，物品有重量 $w$，价值 $c$ 和数量 $d$ 这三个属性，现在要在树上做多重背包，给定重量 $m$，你现在可以选择的物品必须满足在一个连通块内，即如果你选了 $u$ 和 $v$ 中至少一个物品，那么 $u$ 和 $v$ 路径上的每个点你都必须至少选一次

$n\le 500,m\le 4000,w\le m,d\le 100$

简要题解：我们注意到合并两个背包的复杂度为 $O(m^2)$，而插入一个物品的复杂度为 $O(m)$，我们考虑求必须包含根节点的答案，然后按照点分的过程，求不包含当前根节点的答案

我们以 $dfs$ 序的逆序来背包，因为一个点的子树的 $dfs$ 序是一个段区间，我们当前考虑点 $i$，那么我们有两种抉择，不选 $i$，那么 $i$ 的子树也无法选择，那么 $f_i$ 就等于 $f_{i+sz_i}$；强制选择 $i$ 的一个物品，那么 $i$ 的子树可以随便选，那么 $f_i$ 就等于 $f_{i+1}$ 插入 $(w_i,c_i,d_i)$ 这个物品，注意需要保证这个物品至少选 $1$ 个，容易发现这两种情况合并只需要对应位置取 $max$ 即可

时间复杂度 $O(nm\log n)$，如果使用二进制拆分优化多重背包，那么时间复杂度为 $O(nm\log n\log d)$

树上依赖性背包

Luogu P6326 Shopping

树上连通块

CF 486D Valid Sets 对于一个连通块我们可以利用其深度最小的节点来计算贡献

CF 461B Appleman and Tree

树链

简要题意：给定一棵 $n$ 个点的树以及 $m$ 条树上的链，每条链有一个价值，要求选择若干条链，使得每个点至多被包含在一个链中，且价值最大

$n,m\le 2\times 10^5$

简要题解：我们将每条链扔到 $lca$ 上，然后做树形 $dp$

我们令 $f[u]$ 表示 $u$ 子树内已经选择完的最大价值，$g[u]=\sum f[v]$，$v$ 是 $u$ 的儿子

如果 $u$ 没有链，那么 $f[u]=g[u]$；如果 $u$ 有一条链，那么 $f[u]$ 应该取 $g[u]+\sum g[v]-f[v]$，$v$ 是这条链上的点

这个东西做一个差分后相当于区间加和单点查询，可以用树状数组实现，时间复杂度 $O(n\log n)$

CF 856D Masha and Cactus
简要题意：给定一棵 $n$ 个节点的树，每个点有一个权值 $h$，现在要选择若干个点将其染色并赋一个值 $w$，要求染色之后，对于每个点 $x$，都存在两个染过色的点 $u$ 和 $v$，满足 $min\lbrace w_u,w_v\rbrace\ge h_x$ 且 $x$ 位于 $u$ 和 $v$ 的最短路径上，注意 $u$ 不能等于 $v$，如果给一个染色点赋值为 $x$，那么将产生 $x$ 花费，求最小花费

$n\le 2\times 10^5$

简要题解：我们考虑树形 $DP$，但注意到一个点可能被与他没有祖先或儿子关系的点影响，我们首先尝试消除这一点

我们令权值最大的点为根，那么为了覆盖这个根，我们至少要选择它的两个儿子的子树内的点，我们首先默认这点存在

接下来我们开始从下往上做 $dp$，首先我们容易发现，我们只需要给叶子节点染色就行了，那么如果我们要覆盖 $u$，如果子树内目前的值不够，我们只需要选一个最大值提升到 $h_u$ 即可，因为外面还有另一个点，即用来覆盖根的那个点，而对于根，我们直接将最大和次大提升即可

CF 1637F Towers