跳转至

树上背包

有些时候，我们需要把背包容量（\(m\)）分配给树上的节点。并且由于转移的特殊性，我们必须在树上完成 dp（不能摊到序列上）。

树上背包的核心思想是：依次考虑节点的每一棵子树，记录这个前缀的 dp 答案；然后尝试加入一棵新的子树，将这棵子树和原先的前缀合并。

通过某些上下界优化可以将时间复杂度限制在 \(O(nm)\) 级别。

P1272 重建道路

题目大意

给定一棵有根树，切掉树上的一些边，分离一些子树，使剩下的主干上节点数量为 \(P\)，求最少需要切断多少条边。

考虑树上 DP。设 \(f_{u,i}\) 表示在以 \(u\) 为根的子树的主干上保留 \(i\) 个节点，所需要的最小代价。

我们从左到右考虑每一棵子树。对于 \(v\) 子树，我们需要把它和前面的所有子树合并起来。初始时 \(f_{u}\) 表示不考虑 \(u\) 的所有子树（即把它们都砍断）的答案。由此得到 \(f\) 的初值应为

\[ f_{u,i} = \begin{cases} adj[u].size(),&i=1\\ +\infty,&i\ne 1 \end{cases} \]

考虑加入一棵子树 \(v\)：

\[ f'_{u,i} = \min_{k\le i}(f_{u,i}, f_{u,i-k} + f_{v,k} - 1) \]

注意，每次转移时都会考虑到一棵新的子树，此时就需要把预先砍掉的边加回来，所以需要 \(-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
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 155;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

int n, p, ans = INF;
int d[N], f[N][N], size[N];
vector<int> adj[N];

void dfs(int u) {
    f[u][1] = adj[u].size();
    for(auto v : adj[u]) {
        dfs(v);
        for(int i = p; i >= 2; i--) {
            for(int k = 1; k < i; k++) {
                f[u][i] = min(f[u][i], f[u][i - k] + f[v][k] - 1);
            }
        }
    }
    if(u == 1) ans = min(ans, f[u][p]);
    else ans = min(ans, f[u][p] + 1);
}

int main(){

    memset(f, 0x3f, sizeof(f));

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

    dfs(1);

    cout << ans << endl;

    return 0;
}

P3177 [HAOI2015] 树上染色

题目大意

给定一棵 \(n\) 个节点的树，边有边权。给定一个常数 \(m\in [0,n]\)，你需要在这棵树中选择 \(m\) 个点染成黑色，其余点为白色。每个颜色相同的点对 \((u,v)\) 都会产生 \(dis(u,v)\) 的价值，问最大价值和。

\(n\le 2000\)

我们可以将 \(u\rightarrow v\) 的边的贡献交由 \(v\) 统计。我们先将所有子树的信息合并：

\[ f'_{u,j}=\max_{j_1=0}^{j}\{f_{u,j_1}+f_{v,j-j_1}\} \]

然后统计 \(fa[u]\rightarrow u\) 的边产生的贡献：

\[ f'_{u,j}=f_{u,j}+w(fa[u],u) \Big((m-j)j+\big((n-m)-(sz[u]-j)\big)(sz[u]-j)\Big) \]

朴素的转移为 \(O(n^3)\)。我们通过一些上下界优化，可以将时间复杂度优化至 \(O(nm)\)。

具体的，对于 \(f_{u,j}\)，我们应该保证 \(j\le sz[u]\)。因此在转移过程中，我们需要保证 \(j_1\) 不超过当前 \(u\) 已经考虑的子树大小，并且 \(j-j_1\) 不超过 \(v\) 的子树大小 \(sz[v]\)。

分析为 \(O(n^2)\)

合并两棵子树消耗 \(sz[a]sz[b]\) 的时间，可以看作是将两棵子树内的点两两配对。显然，任意两个点只会在 \(lca\) 处被配对一次。时间复杂度不超过 \(O(n^2)\)。

同时，\(j,\ j_1\) 和 \(j-j_1\) 都不能超过 \(m\)。对于子树大小超过 \(m\) 的情况，由于 \(j\) 不能枚举到超过 \(m\) 的位置，因此这种情况等价于 \(sz=m\) 的情况。现在我们只需考虑 \(sz\le m\) 的情况。

分析为 \(O(nm)\)

树上背包

为了方便讨论，不妨将所有树都转换为二叉树的情形，二叉树上的每一个节点都代表一次合并。这个过程会将节点数量增大常数倍。

树上背包2

考虑一次合并，消耗的时间复杂度显然是 \(sz[a]sz[b]\)。不妨设 \(sz[a]\ge sz[b]\)。

  • 对于 \(sz[a]=m\) 的情况，合并之后的子树大小 \(sz'=m=sz[a]\)，等价于我们消耗 \(m\times sz[b]\) 的时间删掉了 \(sz[b]\) 个点；这里均摊 \(O(nm)\)；
  • 同时，如果 \(sz[b]<m\)，容易发现 \(b\) 内部的时间消耗为 \(O(sz[b]^2)\le O(m\times sz[b])\)，可以作为常数直接消去；
  • 对于 \(sz[a]<m\) 且 \(sz[a]+sz[b]\ge m\) 的情况，\(a,b\) 子树内部的复杂度不超过 \(O(m^2)\)，本次合并的时间复杂度也不超过 \(O(m^2)\)；由于这种情况之间没有包含关系，因此最多出现 \(\frac{n}{m}\) 次，总共消耗 \(O(nm)\) 的时间复杂度。
  • 对于 \(sz[a]+sz[b]<m\) 的情况，不断向上跳祖先，找到最靠上的满足 \(sz<m\) 的祖先 \(p\)；\(p\) 子树内部的时间消耗为 \(O(sz[p]^2)\)，这部分时间消耗在 \(p\) 参与的下一次合并中被作为常数去掉了；

因此，如下形式的树上背包，时间复杂度不超过 \(O(nm)\)：

\[ f_{u,j}=\max_{j_1,j_2\le m,\ j_1\le sz[u],\ j_2\le sz[v]}\{f_{u,j_1}+f_{v,j_2}\} \]

其中 \(sz[u]\) 表示当前 \(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
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N = 2010;

struct Edge {
    int v, w;
    int next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, k1, k2;
int sz[N];
int f[N][N];

void dfs(int u, int fa, int fw) {
    sz[u] = 1;
    f[u][0] = 0;
    f[u][1] = 0;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa) continue;
        dfs(v, u, w);
        for(int i = min(k1, sz[u] + sz[v]); i >= 0; i--) {
            for(int j = max(0ll, i - sz[u]); j <= min(min(i, k1), sz[v]); j++) {
                f[u][i] = max(f[u][i], f[u][i - j] + f[v][j]);
            }
        }
        sz[u] += sz[v];
    }
    for(int i = 0; i <= min(k1, sz[u]); i++) {
        f[u][i] += fw * ((k1 - i) * i + (k2 - (sz[u] - i)) * (sz[u] - i));
    }
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(f, -0x3f, sizeof(f));

    cin >> n >> k1;
    k2 = n - k1;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    dfs(1, 0, 0);

    cout << f[1][k1] << endl;

    return 0;
}

qoj5357 芒果冰加了空气

题目大意

给定一棵树，计数它的点分树，不要求分治中心选择在重心。

\(n\le 5000\)

对于一棵点分树，我们切断原树上的任意一条边，都可以得到一种唯一的两个连通块的点分树方案。具体的，设删掉的边为 \((u,v)\)，我们先删去点分树上所有跨过 \((u,v)\) 的边，然后在不改变祖先关系的前提下向两个连通块的点分树中补充一些边，使它们分别连通成一棵树。

考虑在两个连通块之间连接一条边 \((u,v)\)，两棵点分树如何合并。根据上面分裂的过程，我们不难发现，只需要将 \(u,v\) 在点分树上的返根链归并起来，就可以得到合并后的结果。这个过程可以类比 FHQ 的 split 和 merge 的过程。

显然，合并的过程产生的方案数只与 \(u,v\) 在点分树中的深度有关。因此我们记 \(f_{u,j}\) 表示 \(u\) 节点在 \(u\) 子树的点分树中深度为 \(j\)，点分树的方案数。考虑当前点分树中 \(u\) 的返根链中哪些节点是 \(v\) 子树提供的，容易写出转移式：

\[ f'_{u,j}=\sum_{j_1=0}^{j-1}{\Big(f_{u,j-j_1}\big(\sum_{k\ge j_1}f_{v,j_1}\big)\binom{j-1}{j_1}\Big)} \]

这个转移可以做到树上背包 \(O(n^2)\) 的时间复杂度。

代码 
 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
#include<iostream>
#define ll long long
using namespace std;
const int N = 5010;
const int MOD = 1e9 + 7;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n;
int sz[N];
int f[N][N], c[N][N];

void dfs(int u, int fa) {
    f[u][1] = 1;
    sz[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        for(int j = sz[u]; j >= 1; j--) {
            int res = 0;
            for(int j1 = min(j, sz[v]); j1 >= max(0, j - (sz[u] - sz[v])); j1--) {
                (res += (ll)f[u][j - j1] * f[v][j1] % MOD * c[j - 1][j1] % MOD) %= MOD;
            }
            f[u][j] = res;
        }
    }
    for(int i = n - 1; i >= 0; i--) (f[u][i] += f[u][i + 1]) %= MOD;
}

int main() {

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    c[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        c[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        }
    }

    dfs(1, 0);

    cout << f[1][1] << endl;

    return 0;
}