树上背包模型

树上背包模型

树上背包 是 背包问题 在 树结构 上的一种变体，本质仍然是资源分配问题。一个节点的不同孩子对应若干个相互独立的子问题，而父节点负责决定总资源怎样分配给这些孩子，并合并各子树的最优结果。

最基础的子树状态就是“使用多少资源 →\to 取得什么最优结果”。在这个基础上，后面的题目主要讨论两件事：资源可以是什么，以及除了资源数量以外，子树还需要向父节点暴露哪些信息。

一、P2014 选课：资源维从哪里来

问题

P2014 选课
有 nn 门课程，每门课至多有一门直接先修课，要求恰好选择 mm 门课程并满足先修关系，使学分和最大。

数据规模：1≤n,m≤3001\le n,m\le300。

最基础的树形 DP 只需要记录少量父子状态，如 P1352 没有上司的舞会，不过本题要求全局恰好选择 mm 门课。因此子树不能只上传一个最优值，还必须说明这个最优方案占用了多少资源。

定义 f[u][i]f[u][i] 为：在 uu 的子树中选择 ii 个节点，并且选择 uu 时的最大价值。由于不选 uu 就无法选择它的儿子了，所以这个状态不考虑。

处理孩子 vv 时，把最终的 ii 个名额拆成旧部分的 i−ji-j 个和当前孩子 vv 的 jj 个，于是得到 f[u][i]=max⁡(f[u][i],f[u][i−j]+f[v][j])f[u][i] = \max(f[u][i], f[u][i-j] + f[v][j])，这里每个孩子就相当于分组背包中的一个组。

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
29
30
31
32
33
vector<int> adj[maxn];
int val[maxn];
ll f[maxn][maxn];
int n, m;

void dfs( int u ) {
    f[u][1] = val[u];
    for( int v : adj[u] ) {
        dfs( v );
        for( int i = m + 1; i >= 1; -- i ) {
            for( int j = 1; j < i; ++ j ) {
                if( f[u][i-j] == -inf || f[v][j] == -inf ) continue;
                f[u][i] = max( f[u][i], f[u][i-j] + f[v][j] );
            }
        }
    }
}

void solve( ) {
    n = read( ), m = read( );
    for( int i = 1; i <= n; ++ i ) {
        int k = read( );
        val[i] = read( );
        adj[k].push_back( i );
    }
    for( int i = 0; i <= n; ++ i ) {
        for( int j = 0; j <= m + 1; ++ j ) {
            f[i][j] = -inf;
        }
    }
    dfs( 0 );
    cout << f[0][m+1] << '\n';
}

二、资源维可以是什么

P2015 二叉苹果树：从选点到选边

问题

P2015 二叉苹果树
给出一棵带边权二叉树，保留恰好 qq 条边，并要求这些边与根连通，使保留边权总和最大。

数据规模：1≤n≤1001\le n\le100，1≤q<n1\le q<n。

这仍然是一个资源的背包问题，只是资源从点变成了边。根据树的特性，每个点只有一个父亲，所以可以把每条边都下放到它的儿子上。

于是保留 qq 条边就等价于选择 q+1q + 1 个从根节点出发的连通块，最大点权和是多少。父节点仍然只是在决定保留边数怎样分给不同孩子。

所以最后也能转化为一个标准的树上背包模型。当前实现直接合并左右孩子，这是题目保证每个分叉都恰好分成两个孩子的特化；一般多叉树仍然应当按孩子逐个合并。

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
29
30
31
32
33
34
35
36
37
38
39
40
struct Edge { int v, w; };
vector<Edge> adj[maxn];
int val[maxn];
ll f[maxn][maxn];
int n, q;

void dfs( int u, int p ) {
    int l = 0, r = 0;
    for( auto [v, w] : adj[u] ) {
        if( v == p ) continue;
        val[v] = w;
        if( l == 0 ) l = v;
        else r = v;
        dfs( v, u );
    }

    if( l == 0 && r == 0 ) {
        f[u][1] = val[u];
        return;
    }

    for( int j = 1; j <= n; ++ j ) {
        for( int k = 0; k <= j - 1; ++ k ) {
            f[u][j] = max( f[u][j], f[l][k] + f[r][j-k-1] + val[u] );
        }
    }
}

void solve( ) {
    cin >> n >> q;
    for( int i = 1; i < n; ++ i ) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }

    dfs( 1, 0 );
    cout << f[1][q+1] << '\n';
}

P1273 有线电视网：资源与收益来源分离

问题

P1273 有线电视网
叶子节点是用户，用户提供收益，连接边需要支付传输成本。在不亏本的前提下，最大化能够服务的用户数量。

数据规模：2≤N≤30002\le N\le3000，1≤M≤N−11\le M\le N-1，其中 MM 为用户数。

本题也是资源分配类问题，可以采用背包模型。

由于限制条件是不亏本，于是我们可以让 选中的用户数 作为资源，而把净收益作为值，最终找出最大的 jj 使得 f[1][j]≥0f[1][j] \ge 0 即可。

定义 f[u][j]f[u][j] 表示在 uu 子树中选择 jj 个用户时的最大净收益。当从当前孩子 vv 选择 k≥1k\ge1 个用户时，边权 ww 才会被支付，转移为 f[u][j]=max⁡(f[u][j],f[u][j−k]+f[v][k]−w)f[u][j]=\max(f[u][j],f[u][j-k]+f[v][k]-w)。k=0k=0 时保留原状态即可，因此不会为未服务的分支支付传输成本。

其中 kk 表示当前子树 vv 中选择多少个叶子节点，由于在子树中选择了叶子节点，那么这条边的权值是需要收费的。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int n, m;
vector<int> adj[maxn];
int siz[maxn];
ll wei[maxn], val[maxn];
ll f[maxn][maxn];

void dfs( int u, int p ) {
    siz[u] = 1;
    for( int j = 0; j <= m; ++ j ) f[u][j] = -inf;
    f[u][0] = 0;

    if( u > n - m ) {
        f[u][1] = val[u];
        return;
    }

    for( int v : adj[u] ) {
        if( v == p ) continue;
        dfs( v, u );
        siz[u] += siz[v];
        for( int j = min( siz[u], m ); j >= 1; -- j ) {
            for( int k = 1; k <= min( siz[v], j ); ++ k ) {
                if( f[u][j-k] == -inf || f[v][k] == -inf ) continue;
                f[u][j] = max( f[u][j], f[u][j-k] + f[v][k] - wei[v] );
            }
        }
    }
}

void solve( ) {
    n = read( ), m = read( );
    for( int i = 1; i <= n - m; ++ i ) {
        int k = read( );
        for( int j = 1; j <= k; ++ j ) {
            int v = read( ), w = read( );
            adj[i].push_back( v );
            wei[v] = w;
        }
    }
    for( int i = n - m + 1; i <= n; ++ i ) val[i] = read( );

    dfs( 1, 0 );
    for( int j = m; j >= 1; -- j ) {
        if( f[1][j] >= 0 ) {
            cout << j << '\n';
            return;
        }
    }
}

这里资源只统计叶子用户，内部转播站不占资源。原始实现的 siz 只是循环上界的安全估计，非法状态仍由 -inf 排除；若追求紧的复杂度界，应另外维护当前已合并的用户数，而不是把它理解为已选用户数。

选择零个用户的净收益为 00，所以从 mm 到 11 都找不到非负状态时，答案按语义应为 00。保留的原始代码片段只写出了命中正数用户时的输出分支，实际实现需要补上这一兜底输出。

三、P3698 小Q的棋盘：资源之外的接口状态

问题

P3698 小Q的棋盘
从节点 00 出发在树上移动 NN 步，边可以重复经过，求最多能够经过多少个不同节点。

数据规模：1≤V,N≤1001\le V,N\le100。

比较自然的定义是 f[u][j]f[u][j] 表示以 uu 为根的子树中，消耗 jj 步走到的节点个数。

但只记录 “使用了多少步” 不够，因为处理完一个孩子以后，还需要知道棋子是否回到了当前根。

于是扩展状态，定义 f[u][j][0]f[u][j][0] 表示恰好使用 jj 步并回到 uu，f[u][j][1]f[u][j][1] 表示恰好使用 jj 步并最终停在子树某处。f[u][0][0]=f[u][0][1]=1f[u][0][0]=f[u][0][1]=1 时棋子都还在 uu，两个接口暂时重合；只有继续合并孩子以后，它们才产生不同的后续代价。

接着考虑特殊的第三维度合并，综合发现只有 0+0→00 + 0 \to 0，1+0→11 + 0 \to 1，0+1→10 + 1 \to 1 三种情况，不能出现 1+11 + 1，因为一条实际路径不可能同时在两个孩子中留下终点。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int n, m;
vector<int> adj[maxn];
ll f[maxn][maxn][2];

void dfs( int u, int p ) {
    for( int i = 0; i <= m; ++ i ) {
        f[u][i][0] = f[u][i][1] = -inf;
    }
    f[u][0][0] = f[u][0][1] = 1;

    for( int v : adj[u] ) {
        if( v == p ) continue;
        dfs( v, u );

        for( int j = m; j >= 0; -- j ) {
            for( int k = 0; k <= m; ++ k ) {
                if( j-k-2 >= 0 && f[u][j-k-2][0] != -inf && f[v][k][0] != -inf ) {
                    f[u][j][0] = max( f[u][j][0], f[u][j-k-2][0] + f[v][k][0] );
                }
                if( j-k-2 >= 0 && f[u][j-k-2][1] != -inf && f[v][k][0] != -inf ) {
                    f[u][j][1] = max( f[u][j][1], f[u][j-k-2][1] + f[v][k][0] );
                }
                if( j-k-1 >= 0 && f[u][j-k-1][0] != -inf && f[v][k][1] != -inf ) {
                    f[u][j][1] = max( f[u][j][1], f[u][j-k-1][0] + f[v][k][1] );
                }
            }
        }
    }
}

void solve( ) {
    n = read( ), m = read( );
    for( int i = 1; i < n; ++ i ) {
        int u = read( ) + 1, v = read( ) + 1;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    dfs( 1, 0 );

    ll ans = 0;
    for( int j = 0; j <= m; ++ j ) {
        ans = max({ ans, f[1][j][0], f[1][j][1] });
    }
    cout << ans << '\n';
}

Min-Max Tree：有接口状态，不等于树上背包

Min-Max Tree

删除若干树边形成多个连通块，每个连通块的价值为其中最大点权减最小点权，最大化所有连通块的价值总和。

数据规模：1≤n≤1061\le n\le10^6，0≤ai≤1090\le a_i\le10^9。

分析后发现，每个连通块最大的贡献刚好是它是一条链，并且链的两头就是最大点权和最小点权。

于是接着可以设计 DP，分别维护“已经闭合”“留下正开放端”“留下负开放端”三类状态；后两类分别保留一条尚未闭合路径端点所能提供的最大值或最小值。

但它并没有需要在多个孩子之间分配的数量资源，也没有类似 “总量 jj 中给当前孩子 kk” 的转移过程。

因此，“存在额外子树状态” 只能说是树形 DP 的一般特征，并不一定指向树上背包。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
vector<int> adj[maxn];
ll a[maxn];
ll f0[maxn], fp[maxn], fn[maxn];

void dfs( int u, int p ) {
    ll sum = 0;
    for( int v : adj[u] ) {
        if( v == p ) continue;
        dfs( v, u );
        sum += f0[v];
    }

    f0[u] = sum;
    fp[u] = sum + a[u];
    fn[u] = sum - a[u];

    ll mxfp = -inf, mxfn = -inf;
    ll mxpair = -inf;

    for( int v : adj[u] ) {
        if( v == p ) continue;

        ll pval = fp[v] - f0[v];
        ll nval = fn[v] - f0[v];

        if( mxfn != -inf ) mxpair = max( mxpair, pval + mxfn );
        if( mxfp != -inf ) mxpair = max( mxpair, nval + mxfp );

        mxfp = max( mxfp, pval );
        mxfn = max( mxfn, nval );

        f0[u] = max({ f0[u], sum - f0[v] + fp[v] - a[u],
                              sum - f0[v] + fn[v] + a[u] });
        fp[u] = max( fp[u], sum - f0[v] + fp[v] );
        fn[u] = max( fn[u], sum - f0[v] + fn[v] );
    }

    if( mxpair != -inf ) f0[u] = max( f0[u], sum + mxpair );
}

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );

    for( int i = 1; i < n; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    dfs( 1, 0 );
    cout << f0[1] << '\n';
}

四、P3177 树上染色：先改写目标函数

问题

P3177 树上染色
在带权树上选择恰好 mm 个点染黑，其余点染白。收益为所有黑点对距离之和加上所有白点对距离之和，求最大收益。

数据规模：0≤m≤n≤20000\le m\le n\le2000，1≤w≤1041\le w\le10^4。

原目标函数是求全局相同颜色点对的距离，这个很难直接按子树求和。

不过可以利用树上任意两点之间的路径是唯一的，可以把每一对点的距离拆到经过的边上，从边的角度计数。

设儿子子树大小为 ss，其中选择了 kk 个黑点，那么父亲方向就有 m−km - k 个黑点。两个方向的白点数分别为 s−ks - k 以及 (n−s)−(m−k)(n - s) - (m - k) 个，于是这条边的贡献就是 [k(m−k)+(s−k)(n−s−m+k)]w[k(m-k)+(s-k)(n-s-m+k)]w。

计算到这里，就可以解决背包资源对应的价值了，接着跑一次树上背包就可以解决了。

注意 k=0k = 0 需要单独处理，因为儿子选择 00 个时，原状态和目标状态相同，会被重复合并。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int n, m;
struct Edge { int v; ll w; };
vector<Edge> adj[maxn];
int siz[maxn];
ll f[maxn][maxn];

void dfs1( int u, int p ) {
    siz[u] = 1;
    for( auto [v, w] : adj[u] ) {
        if( v == p ) continue;
        dfs1( v, u );
        siz[u] += siz[v];
    }
}

void dfs2( int u, int p ) {
    f[u][0] = f[u][1] = 0;

    for( auto [v, w] : adj[u] ) {
        if( v == p ) continue;
        dfs2( v, u );

        for( int j = min( m, sz[u] ); j >= 0; -- j ) {
            if( f[u][j] != -1 ) {
                f[u][j] += f[v][0] + (ll)sz[v] * ( n-m-sz[v] ) * w;
            }

            for( int k = min( j, sz[v] ); k >= 1; -- k ) {
                if( f[u][j-k] == -1 ) continue;
                ll tot = ( k * ( m-k ) + ( sz[v]-k ) * ( n-sz[v]-m+k ) ) * w;
                f[u][j] = max( f[u][j], f[u][j-k] + f[v][k] + tot );
            }
        }
    }
}

void solve( ) {
    n = read( ), m = read( );
    for( int i = 1; i < n; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }

    memset( f, -1, sizeof f );
    dfs1( 1, 0 );
    dfs2( 1, 0 );

    cout << f[1][m] << '\n';
}

五、P2515 软件安装：先压缩依赖结构

问题

P2515 软件安装
每个软件有容量和价值，并且至多依赖另一个软件。依赖关系可能成环，在总容量限制下最大化能够正常工作的软件总价值。

数据规模：0≤N≤1000\le N\le100，0≤M≤5000\le M\le500，0≤Wi≤M0\le W_i\le M，0≤Vi≤10000\le V_i\le1000。

环内的软件必须一起选择，因此先用 SCC 把整个强连通分量压成一个物品，并把容量与价值分别求和。由于每个软件至多有一个直接依赖，缩点后的每个块也至多有一个父块，再用虚拟根连接所有根块，就得到可以进行树上背包的依赖树。

这题的新增不在背包转移，而在进入 DP 之前的结构处理。SCC 缩点 不仅能去环，还能把原来的依赖图压缩成适合树上背包的结构。当前 dp[u][j] 表示容量不超过 jj 时的最大价值，因为基础状态会对所有 j≥scc_wei[u]j\ge scc\_wei[u] 写入同一个分量价值。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
vector<int> adj[maxn], dag[maxn];
stack<int> st;
int dfn[maxn], low[maxn], timer;
bool in_stack[maxn];
int scc[maxn], scc_cnt;
int fa[maxn], indeg[maxn];
ll val[maxn], scc_val[maxn];
ll wei[maxn], scc_wei[maxn];
ll dp[maxn][maxm];
int n, m;

void dfs( int u ) {
    for( int j = scc_wei[u]; j <= m; ++ j ) {
        dp[u][j] = scc_val[u];
    }

    for( int v : dag[u] ) {
        dfs( v );
        for( int j = m; j >= scc_wei[u]; -- j ) {
            for( int k = 0; k <= j - scc_wei[u]; ++ k ) {
                dp[u][j] = max( dp[u][j], dp[u][j-k] + dp[v][k] );
            }
        }
    }
}

void tarjan( int u ) {
    dfn[u] = low[u] = ++ timer;
    st.push( u );
    in_stack[u] = 1;

    for( int v : adj[u] ) {
        if( !dfn[v] ) {
            tarjan( v );
            low[u] = min( low[u], low[v] );
        } else if( in_stack[v] ) {
            low[u] = min( low[u], dfn[v] );
        }
    }

    if( low[u] == dfn[u] ) {
        ++ scc_cnt;
        int v;
        do {
            v = st.top( );
            st.pop( );
            in_stack[v] = 0;
            scc[v] = scc_cnt;
            scc_val[scc_cnt] += val[v];
            scc_wei[scc_cnt] += wei[v];
        } while( v != u );
    }
}

void solve( ) {
    cin >> n >> m;
    for( int i = 1; i <= n; ++ i ) cin >> wei[i];
    for( int i = 1; i <= n; ++ i ) cin >> val[i];

    for( int i = 1; i <= n; ++ i ) {
        cin >> fa[i];
        if( fa[i] == 0 ) continue;
        adj[fa[i]].push_back( i );
    }

    for( int i = 1; i <= n; ++ i ) {
        if( !dfn[i] ) tarjan( i );
    }

    for( int u = 1; u <= n; ++ u ) {
        int v = fa[u];
        if( v == 0 || scc[u] == scc[v] ) continue;
        dag[scc[v]].push_back( scc[u] );
        indeg[scc[u]] ++;
    }

    for( int i = 1; i <= scc_cnt; ++ i ) {
        if( indeg[i] == 0 ) dag[0].push_back( i );
    }

    dfs( 0 );
    cout << dp[0][m] << '\n';
}

六、复杂度与实现

树上背包通常按孩子逐个合并。处理当前孩子 vv 时，枚举最终资源量 jj 和分给 vv 的资源量 kk，把“已经处理的孩子”和“当前孩子”合成新的状态；原地更新时通常倒序枚举 jj，避免一个孩子被重复使用。

复杂度不能只看代码有几层循环。真正需要统计的是每次合并时，有多少组“旧部分资源量 + 当前孩子资源量”的合法配对；使用子树规模限制可以减少大量无效状态，但具体复杂度仍应根据题目的资源含义单独分析。

另外还要区分“恰好使用 jj 个资源”和“最多使用 jj 个资源”。P2014 的答案要求恰好选够课程，而 P3698 最终可以在所有步数不超过预算的状态中取最大值，两者的答案读取方式并不相同。

七、小结

树上背包可以先用一句话识别：

摘要

不同孩子内部可以独立求解，但它们共同竞争某个可加的有限资源；每个子树向父节点提供不同资源占用量下的最优方案，父节点再重新分配资源并合并这些方案。

遇到新题时，可以依次检查：

  1. 不同孩子在固定接口以后是否独立？
  2. 是否存在一个需要在孩子之间分配的有限资源？
  3. 子树在使用 jj 个资源时，应该向父节点汇报什么最优结果？
  4. 资源数量之外，还有哪些信息会影响未来合并？
  5. 目标函数能否直接按子树计算，还是需要先改变贡献表示？
  6. 原始依赖结构是不是树，若不是，能否先压缩结构？
  7. 状态表示恰好使用资源，还是不超过资源预算？
  8. 复杂度真正枚举了多少组合法资源分配？

其中 P1352 这类只有父子状态分类、没有跨孩子资源分配的普通树形 DP，不属于这里讨论的树上背包。Min-Max Tree 同样说明，子树存在有限接口状态，也不足以单独构成树上背包。

相关导航：动态规划导览 · 算法与竞赛

旧算法 > 动态规划
#algorithm/题型 #DP/树形 #DP/树上背包
树上背包模型
http://miqiu.space/posts/treeknap26/
作者
Miqiu
发布于
2026年8月29日
许可协议