DDOSvoid's Blog

Luogu P6326 Shopping

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P6326

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

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

Solution

我们注意到合并两个背包的复杂度为 $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)$

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 510
#define maxm 4010
#define ll long long
using namespace std;

int n, m, w[maxn], c[maxn], d[maxn];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

bool vis[maxn];
namespace DF {
    int f[maxn], sz[maxn];
    int sum, rt;

    void init(int n) { f[rt = 0] = n + 1; fill(vis + 1, vis + n + 1, false); }
    void dfs_sz(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 || vis[v]) continue;
            dfs_sz(v, u); sz[u] += sz[v];
        }
    }
    void dfs(int u, int fa) {
        f[u] = 0; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (v == fa || vis[v]) continue;
            dfs(v, u); f[u] = max(f[u], sz[v]); 
        } f[u] = max(f[u], sum - sz[u]);
        if (f[u] < f[rt]) rt = u; 
    }
    inline int get_rt(int u) {
        rt = 0; dfs_sz(u, 0);
        sum = sz[u]; dfs(u, 0); return rt;
    }
}

struct node {
    int a[maxm];

    node() {}
    void clear() { fill(a, a + m + 1, 0); }
    void insert(int w, int c, int d) {
        for (int j = m; j; --j) a[j] = (j >= w ? a[j - w] + c : 0); --d;
        for (int i = 1; i <= d; d -= i, i <<= 1) 
            for (int j = m; j >= i * w; --j) a[j] = max(a[j], a[j - i * w] + i * c);
        if (d)
            for (int j = m; j >= d * w; --j) a[j] = max(a[j], a[j - d * w] + d * c);
    }
    void update(const node &t) { for (int i = 0; i <= m; ++i) a[i] = max(a[i], t.a[i]); }
} f[maxn];

int id[maxn], bl[maxn], sz[maxn], cnt;
void dfs(int u, int fa) {
    id[u] = ++cnt, bl[cnt] = u; sz[u] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || vis[v]) continue;
        dfs(v, u); sz[u] += sz[v];
    }
}

int ans;
void divide(int u) {
    vis[u] = 1, cnt = 0, dfs(u, 0);
    for (int i = 1; i <= cnt; ++i) f[i].clear(); f[cnt + 1].clear();
    for (int i = cnt, u = bl[i]; i; u = bl[--i]) {
        f[i] = f[i + sz[u]];
        node tmp = f[i + 1]; tmp.insert(w[u], c[u], d[u]);
        f[i].update(tmp);
    } ans = max(ans, f[1].a[m]);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (vis[v]) continue;
        divide(DF::get_rt(v));
    }
}

void work() {
    cin >> n >> m;
    fill(head + 1, head + n + 1, -1), c1 = 0;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= n; ++i) cin >> d[i];
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y), add_edge(y, x); 
    } DF::init(n), ans = 0, divide(DF::get_rt(1));
    cout << ans << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}