树上背包学习笔记

一、什么是树上背包？

树上背包可以理解为：在树形 DP 的基础上，把多个儿子的子树状态逐个合并，得到当前节点的状态。

普通背包考虑的是物品的选择，而树上背包考虑的是如何把不同子树的状态合并起来。

一般分为三个步骤：

  1. 递归处理每个儿子。

  2. 枚举当前已经处理的部分和儿子子树的状态，进行背包合并。

  3. 更新当前子树的大小 siz[u]。

树上背包的核心是：

状态定义 + 初始化 + 枚举合并 + 更新子树大小。

二、状态定义

常见的状态定义：

f[u][j] 表示以 u 为根的子树中，选择 j 个节点时的最优值。

根据题目不同，最优值可以是：

  • 最大价值

  • 最小代价

  • 最大收益

  • 方案数量

siz[u] 表示以 u 为根的子树包含的节点数量。

注意：状态定义需要根据题意确定，并不是所有树上 DP 都必须使用 siz[u]。

三、核心转移：j-k 与 j+k

两种写法本质相同，区别只是 j 的含义不同。

1. j-k 写法：先确定最终状态

1
2
f[u][j]=max(f[u][j],
            f[u][j-k]+f[v][k]);

其中：

  • j：合并后的目标状态。

  • k：从儿子 v 的子树中选择的节点数。

  • j-k：原来已经处理的部分选择的节点数。

因为：

$$
(j-k)+k=j
$$

所以可以从 f[u][j-k] 和 f[v][k] 转移到 f[u][j]。

这种写法和经典背包比较接近，适合先确定最终状态，再拆分两部分的贡献。

2. j+k 写法：先确定两部分

1
2
f[u][j+k]=max(f[u][j+k],
              f[u][j]+f[v][k]);

其中：

  • j：合并前已经处理的部分选择的节点数。

  • k：儿子子树选择的节点数。

  • j+k：合并后的节点总数。

因为：

$$
j+k=\text{合并后的节点数}
$$

所以直接更新 f[u][j+k]。

3. 两种写法的对比

假设最终需要选择 5 个节点：

原来部分 儿子部分 最终状态
4 1 5
3 2 5
2 3 5
1 4 5

j-k：先固定最终状态 5，再枚举两部分的数量。

j+k：先枚举两部分的数量，再计算最终状态。

两者枚举的是同一批组合，k 始终表示儿子子树贡献的数量。

四、树上背包的基本模板

统一约定： 本节的两个模板都求最大值，非法（不可达）状态必须初始化为负无穷，并且初始化和判断要用同一个常量。

1
2
const ll NEG = -1e18;   // 最大值 DP 的非法状态：负无穷
const ll INF =  1e18;   // 最小值 DP 的非法状态：正无穷

注意不要写成 const int inf = 0x3f3f3f3f; 再拿去做 max：max(正无穷, 合法值) 还是正无穷，合法状态永远写不进 f；反过来做 min 时把非法状态设成负无穷也会出同样的问题。

j-k

下面使用 j-k 写法，假设：

  • f[u][j] 表示选择 j 个节点的最大价值。

  • f[v][k] 表示儿子子树选择 k 个节点的最大价值。

  • 当前节点 u 必须被选择。

  • 合并时没有额外的边权贡献。

  • f[u][0] 和 f[v][0] 均表示合法的空选择，但当前节点必须被选择，所以 u 自身的初始状态为 f[u][1]=0。

转移方程：
$$
f[u][j]=\max\left(f[u][j],f[u][j-k]+f[v][k]\right)
$$

其中：

  • j：合并之后选择的节点总数。

  • k：从儿子子树中选择的节点数。

  • j-k：原来已经处理的部分（合并前）选择的节点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void dfs(int u,int p)
{
    siz[u]=1;
    f[u][1]=0;              // 其余 f[u][*] 统一初始化为 NEG
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
        for(int j=min(m,siz[u]+siz[v]);j>=1;--j){
            for(int k=max(0,j-siz[u]);k<=min(siz[v],j-1);++k){
                if(f[u][j-k]==NEG || f[v][k]==NEG) continue;
                f[u][j]=max(f[u][j],
                            f[u][j-k]+f[v][k]);
            }
        }
        siz[u]+=siz[v];
    }
}

j-k：从当前已经合并好的部分中选择的节点数。
如果j-k大于原来的siz[u]状态就是错的，所以k=max(0,j-siz[u])
注意：这是帮助理解合并过程的基本框架。具体题目需要根据状态定义调整初始化、空选择是否合法、转移范围以及额外贡献。

j+k

下面使用 j+k 写法，假设：

  • f[u][j] 表示以 u 为根的子树中，选择 j 个节点的最大价值。

  • f[v][k] 表示以儿子 v 为根的子树中，选择 k 个节点的最大价值。

  • 当前节点 u 必须被选择，因此初始化 f[u][1]=w[u]。

  • 合并时，将儿子子树中选择的 k 个节点与当前已经选择的 j 个节点合并，得到 j+k 个节点。

合并儿子 v 之前，f[u][j] 表示已经处理过的部分；f[v][k] 表示儿子子树的状态。

转移方程：
$$
f[u][j+k]=\max\left(f[u][j+k],f[u][j]+f[v][k]\right)
$$

其中：

  • j：当前已经选择的节点数。

  • k：从儿子子树中选择的节点数。

  • j+k：合并之后选择的节点总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int u,int p)
{
    siz[u]=1;
    f[u][1]=w[u];           // 其余 f[u][*] 初始化为 NEG
    for(auto v:adj[u])
    {
        if(v==p) continue;
        dfs(v,u);
		for(int j=min(siz[u],m);j>=1;--j){
			if(f[u][j]==NEG) continue;
		
			for(int k=1;k<=min(siz[v],m-j);++k){
				if(f[v][k]==NEG) continue;
		
				f[u][j+k]=max(f[u][j+k],
							  f[u][j]+f[v][k]);
			}
		}
	    siz[u]+=siz[v];
    }
}

为什么 j 要倒序枚举？

每次合并一个儿子时，f[u] 表示已经合并的部分，f[v] 表示新加入的儿子子树。

对于 j+k 的原地合并，当 k>0 时，倒序枚举 j 可以避免本轮刚更新出的较大下标状态再次作为来源。若 k=0，需要根据状态含义单独处理。(类似01背包)

如果允许不选择儿子子树中的任何节点，还需要考虑 k=0 的情况。

写法的区别

对比 j-k 写法 j+k 写法
状态转移 f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]) f[u][j+k] = max(f[u][j+k], f[u][j] + f[v][k])
含义 从总数 j 中分配 k 个给儿子 将已有的 j 个与儿子的 k 个合并
常见枚举 j 倒序，k 从小到大 j 倒序，k 从小到大
关键区别 枚举合并后的总数 j 枚举合并前的数量 j

两种写法在数学上可以等价，但原地更新时，不能只凭公式判断是否安全，还必须看循环顺序和状态是否会被重复使用。

五、临时数组 ndp：更容易保证正确

如果无法确认原地更新是否安全，建议使用临时数组 ndp。

使用临时数组，可以把合并前的状态和合并后的状态分开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void dfs(int u,int p)
{
    siz[u]=1;
    f[u][1]=0;              // 其余 f[u][*] 统一初始化为 NEG

    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
        vector<ll> ndp(siz[u]+siz[v]+1,NEG);   // 非法状态必须和 f 用同一个常量

        for(int j=1;j<=min(siz[u],m);++j){
            if(f[u][j]==NEG) continue;
            
            for(int k=0;k<=min(siz[v],m-j);++k){
                if(f[v][k]==NEG) continue;
                
                ndp[j+k]=max(ndp[j+k],
                             f[u][j]+f[v][k]);
            }
        }
        
		siz[u]+=siz[v];
        for(int j=1;j<=min(siz[u],m);++j){
            f[u][j]=ndp[j];
        }

    }
}

这种写法的优点：

  • f[u] 保存合并前的状态。

  • ndp 保存本次合并后的状态。

  • 不会把本轮新生成的状态再次作为本轮的来源。

注意：该代码假设 u 必须被选择，因此没有保留 f[u][0]；如果题目允许不选当前节点，需要重新设计初始化和状态转移。

另外，ndp 的初值必须和 f 用同一个非法常量（这里是 NEG）。如果图省事写成 0，搬回 f[u] 之后所有不可达状态都会变成“值为 0 的合法状态”，f[u][j]==NEG 的判断就永久失效了；权值可能为负、或者求最小值时，答案会直接错。

例题一：P1272 重建道路

1. 状态定义

f[u][j] 表示在 u 的子树中保留 j 个节点，并使它们连通所需要删除的最少边数。

2. 转移方程

1
2
f[u][j]=min(f[u][j],
            f[u][j-k]+f[v][k]-1);

其中：

  • j：最终保留的节点数量。

  • k：儿子子树保留的节点数量。

  • j-k：原来已经处理的部分保留的节点数量。

为什么减去 1？

因为分别计算两部分时，连接 u 和 v 的边被算作需要删除的边；合并后，这条边应该保留，所以要减去 1。

3. 循环框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int u,int p){
    siz[u]=1;f[u][1]=adj[u].size();//把自己直接相连的孩子剪掉也就是adj[u].size()-1
    if(p!=0) f[u][1]--;
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
        for(int j=siz[u]+siz[v];j>0;--j){
            for(int k=min(siz[v],j-1);k>0;--k){
                f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]-1);
            }
        }
        siz[u]+=siz[v];
    } 
}

由于要求保留的节点连通：

  • 原来的部分至少保留一个节点。

  • 儿子子树也至少保留一个节点。

因此这里 k>=1，且 j-k>=1。

初始化、父边的处理和最终答案需要根据原题要求单独处理（本题是最小值 DP，非法状态用正无穷，例如 const ll INF=1e18;，与上面的 NEG 正好相反）。

例题二：P3177 树上染色

1. 状态定义

f[u][j] 表示 u 的子树中选择恰好 j 个黑点时，子树内部所有边的最大贡献。

2. 转移方程

1
2
f[u][j]=max(f[u][j],
            f[u][j-k]+f[v][k]+w*sum);

其中：

  • j：合并后的黑点总数。

  • k：儿子子树中的黑点数。

  • j-k：原来已经处理的部分中的黑点数。

3. 边的贡献

1
2
ll sum=k*(m-k)
       +(siz[v]-k)*(n-siz[v]-m+k);

经过边 (u,v) 的路径数量（黑黑点对 + 白白点对），等于这条边两侧颜色相同的点对数量。

因此：

1
w*sum

就是这条边对答案的贡献。

合并儿子时，将它加入转移即可。

4. 循环框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int u,int p){
    siz[u]=1;
    for(auto [v,w]:adj[u]){
        if(v==p) continue;
        dfs(v,u);
        for(int j=min(m,siz[u]+siz[v]);j>=0;--j){
            for(int k=max(0,j-siz[u]);k<=min(siz[v],j);++k){
                ll sum=k*(m-k)+(siz[v]-k)*(n-siz[v]-m+k);
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+w*sum);
            }
        } 
        siz[u]+=siz[v];
    }
}

注意：本题的状态和边贡献依赖于全树恰好选择 m 个黑点的条件，因此 sum 不能直接照搬到其他树上背包题目。

例题三：CCPC 模拟新赛制 K

1. 状态定义

f[u][j] 表示以 u 为根，在其子树中选择一个包含节点 u 的连通点集，且点集内所有节点的 a 值之和恰好为 j 的方案数。

由于每个节点的 a[u] 为 0 或 1，初始化如下：

1
2
if(a[u]==1) f[u][1]=1;
else f[u][0]=1;

含义：

  • 如果 a[u]=1，只选择节点 u 时，点权和为 1。

  • 如果 a[u]=0，只选择节点 u 时，点权和为 0。

注意：虽然点权和可能为 0，但所选点集仍然必须包含节点 u。

2. 转移方程

假设当前正在合并节点 u 的儿子 v。

  • j：当前已经处理的部分，其点权和为 j。

  • kk：从儿子 v 的子树中选择一个包含 v 的连通点集，其点权和为 kk。

  • j+kk：合并后的点权和。

转移方程：

1
f[u][j+kk]=(f[u][j+kk]+f[u][j]*f[v][kk])%mod;

为什么可以直接相乘？

因为当前部分的选择方案与儿子子树中的选择方案相互独立，任意一种当前方案都可以与任意一种儿子方案组合，因此方案数相乘。

为什么还要加上原来的 f[u][j+kk]？

因为原来可能已经存在点权和为 j+kk 的方案，现在需要把新合并得到的方案数累加进去。

3. 循环框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int u,int p)
{
    siz[u]=1;
    if(a[u]==1) f[u][1]=1;
    else f[u][0]=1;
    
    for(int v:adj[u])
    {
        if(v==p) continue;
        dfs(v,u);

        for(int j=min(siz[u],k);j>=0;--j)
        {
            if(!f[u][j]) continue;
            ll cur=f[u][j];
            for(int kk=0;kk<=min(k-j,siz[v]);++kk)
            {
                f[u][j+kk]=(f[u][j+kk]+cur*f[v][kk])%mod;
            }
        }
        siz[u]+=siz[v];
    }
}

这里有几个需要注意的地方：

  • j 倒序枚举，避免本次合并刚更新出的状态被再次使用。

  • kk 从小到大枚举，表示儿子子树所选连通点集的点权和。

  • cur 保存合并前的 f[u][j]，避免 kk=0 时更新当前状态后影响后续计算。

  • kk=0 不能省略，因为点权为 0 的节点也可能构成合法的连通点集。

  • siz[u] 统计当前已经处理的子树节点数，用于限制状态范围。

常见错误总结

1. 循环范围超过实际需要

如果最终只需要选择 m 个节点，就没有必要枚举超过 m 的状态。

2. 初始化不正确

  • 最大值 DP：非法状态通常设为负无穷。

  • 最小值 DP：非法状态通常设为正无穷。

  • 方案数 DP：非法状态通常设为 0，合法初始状态设为 1。

3. 忘记题目特殊限制

例如：

  • 连通性要求可能导致 k 不能为 0。

  • 必须选根节点时，f[u][0] 可能非法。

  • 某些题目合并边时需要额外计算贡献。

4. 原地更新导致重复使用状态

如果不确定原地更新是否安全，可以使用临时数组 ndp。

5. 原地更新与临时数组

树上背包不一定需要临时数组。是否可以原地更新，取决于状态转移和枚举顺序。

  • j+k 写法： 倒序枚举 j，通常可以避免当前儿子刚产生的状态再次作为来源。若 k=0，需要根据状态含义处理，并在必要时保存旧状态。

  • j-k 写法： 倒序枚举目标状态 j，当 k>0 时，来源状态 f[u][j-k] 的下标小于 j，通常还未在本轮合并中更新，因此可以原地转移。

  • 临时数组： 使用 ndp 保存合并后的状态，可以明确区分合并前后的数据，降低原地更新出错的风险。

  • 注意空选择： k=0 是否合法取决于状态定义。空集不等于包含儿子 v、但点权和为零的连通点集。

判断原地更新是否安全时，不要只记住“正序”或“倒序”，而要检查来源状态是否可能被本轮更新污染，以及当前儿子的贡献是否会被重复使用。

比赛时的思考流程

遇到树上背包时，按下面的顺序分析：

  1. 定义状态： f[u][j] 表示什么？

  2. 确定初始化： 只选 u 时，哪些状态合法？

  3. 递归儿子： 先得到 f[v][k]。

  4. 记录旧大小： old=siz[u]。

  5. 枚举状态： 明确 j 是目标状态还是合并前的状态。

  6. 写转移： 使用 j-k 或 j+k。

  7. 处理额外贡献： 例如边权、连通性约束。

  8. 更新大小： siz[u]+=siz[v]。

  9. 检查边界： 防止越界和非法状态参与转移。

  10. 计算答案： 确认答案来自根节点还是所有节点。

记住：状态定义决定转移方程，初始化决定哪些状态合法，循环范围决定哪些组合可以参与合并。