Tree DP

1、基础树形 DP

树形 DP 处理的问题是在树上计算某值的最优解(如最小值)或方案数等问题,通常会有父子节点之间的关系作为限制条件。
譬如说,要在树上选一些点,要求对任意点不能同时选择它和它的父节点,求选出的点的最大点权和。这就是一个典型的树上 DP 问题。
通常来说,我们设计的状态是:$dp[u][…]$
它的含义是,以 $u$ 为根节点的子树中,满足某条件的某值。后面的省略号代表还会有其他的维数,具体因题目而异。
在转移的时候,通常有两种方法:

  1. 每个节点的 DP 值是由其父节点的 DP 值推出来的。
  2. 每个节点的 DP 值是由其各个子树的 DP 值合并而来的。
    这两种方法都需要用 DFS 来实现。
1
2
3
4
5
6
7
8
9
10
void dfs(int u,int fa){
//3
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
//1
dfs(v,u);
//2
}
}

这个 DFS 的框架与正常 DFS 无异,注意的是注释 1 ,2 和 3 处。
注释 1 处理的第一种情况,即每个节点的 DP 值是由其父节点的 DP 值推出来的。此时节点 u 的 DP 值已经算出来了,这里就是处理 v 的 DP 值。
注释 2 处理的第二种情况,即每个节点的 DP 值是由其各个子树的 DP 值合并而来的。此时前面已经递归完了,也就是说 u 的子树里的所有节点的 DP 值都算出来了,在这里合并子树中的信息,得到 u 的 DP 值。
可以发现,第二种情况的实质是从叶子反着推回根,所以我们需要初始化叶子节点。而注释 3 就是实现这一功能的地方,有些时候别的节点也需要初始化。
对于前面说的那个在树上选一些点,要求对任意点不能同时选择它和它的父节点,求选出的点的最大点权和的问题,代码就是这样的:

1
2
3
4
5
6
7
8
9
10
void dfs(int u,int fa){
    dp[u][1]=r[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0]+=max(dp[v][1],dp[v][0]);
        dp[u][1]+=dp[v][0];
    }
}

$dp[u][0/1]$ 为:以 $u$ 为根的子树中,不选/选节点 $u$ 的最大点权和。

2. 树上背包

例题:在树上选 $m$ 个节点,如果选择了某个节点,那么它的父节点也必须选,求选出的 $m$ 个节点的最大点权和

与正常的一维背包相似,设 $dp[u][i][j]$ 为:以 $u$ 为根的前 $i$ 个子树内选 $j$ 个节点的最大点权和。
滚动数组可以将那个“$[i]$”优化掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dfs(int u) { 
int p=1;
dp[u][1]=s[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dfs(v);
for(int j=m;j>0;j--)
for(int k=0;k<j;k++)
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
//dp[u][j]为之前的最优解
//dp[u][j-k]+dp[v][k]为在v中选k个节点的点权和
}
return p;
}

$s$ 是点权。此处类似于多重背包,需要枚举以 $v$ 为根的子树中选几个节点。

3. 换根 DP

此时根不固定,考虑对于每个节点,当它为根时,某值是怎样的。

例题:给定一个 $n$ 个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大。一个结点的深度之定义为该节点到根的简单路径上边的数量。

我们的思路是:做 2 个 DFS。
还是假定 1 为根
第一个 DFS 处理出 $dp_1$,即以 1 为根时所有点的深度,然后再处理出以 1 为根时,每个节点子树的大小(设 $cnt_i$ 为以 $i$ 为根的子树的大小)。
在第二个 DFS 中,考虑当 $dp_u$ 确定了之后,如何算出 $dp_v$,其中 $v$ 是 $u$ 的儿子,两节点之间的边权为 $w$。
我们发现,当根从 $u$ 转到 $v$ 时,$v$ 的子树内的所有节点(共 $cnt_v$ 个)的深度都会减少 $w$,因为它们距离 $v$ 比距离 $u$ 近了 $w$。而不在 $v$ 的子树内的节点(共 $n-cnt_v$ 个)的深度都会增加 $w$,因为它们距离 $v$ 比距离 $u$ 远了 $w$。
所以,$dp_v=dp_u-w\times cnt_v+w\times (n-cnt_v)$
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int u,int fa){
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
siz[u]+=siz[v];
}
}
void dfs2(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dp[v]=dp[u]-e[i].w*siz[v]+e[i].w*(n-siz[v]);
dfs2(v,u);
}
}

注意,第一个 DFS 执行完之后,先算出 $dp_1$ 的值,再执行第二个 DFS。


Tree DP
https://cwhirly.github.io/2024/12/19/OI/Dynamic Programming/Tree DP/
作者
Weihao Cheng
发布于
2024年12月19日
许可协议