非常好题目。
思路
考虑题目需要求一个连通块的背包。
点分治是平凡的，很容易想到，因为要统计的东西恰好可以把树分成几段。
但点分治操作时的背包确实卡了一下。
以前也没有见过这样的做法。
我们考虑如果直接做树上背包的话。
复杂度是绝对受不了的。
因为合并两个多重背包是基于值域的。
无法体现在树上的优势。
这个时候，就可以用一种新的巧妙思路。
-
我们考虑进入某个节点时，将此时的背包存下来。
-
然后先强制选一个物品。
-
再对当前节点做多重背包，可以使用二进制优化。
-
继续遍历后面的儿子。
-
离开时将每个值与进入是所存储的值取较小值。
然后发现我们的背包的复杂度惊人的变成了 \(O(nm\log v)\)。
好像这个东西被称为树上依赖性背包。
个人感觉确实比较巧妙。
最终时间复杂度 \(O(nm\log v\log n)\)。
Code
/**
* @file P6326.cpp
* @author mfeitveer
* @date 2023-11-24
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 510;
const int M = 4010;
const int mod = 998244353;
int n, m, w[N], c[N], d[N], dp[M];
int rt, rtsz, sz[N], mz[N], vs[N], ans;
vector<int> to[N];
inline void frt(int x, int fa)
{
sz[x] = 1, mz[x] = 0;
for(auto i : to[x])
{
if(i == fa || vs[i]) continue;
frt(i, x), sz[x] += sz[i];
mz[x] = max(mz[x], sz[i]);
}
mz[x] = max(mz[x], rtsz - sz[x]);
if(mz[x] < mz[rt]) rt = x;
}
inline void dfs(int x, int fa)
{
sz[x] = 1;
int f[M], sy = d[x];
memcpy(f, dp, sizeof(dp));
pre(j, m, c[x]) dp[j] = dp[j - c[x]] + w[x];
fro(j, 0, c[x] - 1) dp[j] = -2e7; sy--;
for(int i = 1;sy;i <<= 1)
{
int r = min(i, sy); sy -= r;
int y = c[x] * r, z = w[x] * r;
pre(j, m, y) dp[j] = max(dp[j], dp[j - y] + z);
}
for(auto i : to[x])
{
if(vs[i] || i == fa) continue;
dfs(i, x), sz[x] += sz[i];
}
fro(j, 0, m) dp[j] = max(dp[j], f[j]);
}
inline void calc(int now)
{
memset(dp, 0, sizeof dp), dfs(now, 0);
fro(i, 0, m) ans = max(ans, dp[i]);
}
inline void solve(int now)
{
vs[now] = 1, calc(now);
for(auto i : to[now])
{
if(vs[i]) continue;
rt = 0, rtsz = sz[i];
frt(i, now), solve(rt);
}
}
inline void solve()
{
cin >> n >> m, ans = 0;
fro(i, 1, n) cin >> w[i];
fro(i, 1, n) cin >> c[i];
fro(i, 1, n) cin >> d[i];
fro(i, 1, n - 1)
{
int x, y;
cin >> x >> y;
to[x].eb(y), to[y].eb(x);
}
rtsz = mz[rt = 0] = n, frt(1, 0), solve(rt);
cout << ans << endl;
fro(i, 1, n) to[i].clear();
memset(vs, 0, sizeof vs);
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 125;
cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
int t; cin >> t;
while(t--) solve();
return 0;
}