P3780 [SDOI2017] 苹果树

· · 题解

P3780 [SDOI2017] 苹果树

问题相当于选择从根到某个点的路径，免费选一个苹果，再做 树上依赖性背包。这个点肯定是叶子，因为多选免费苹果一定更优。

设 f 表示当前可以继续往下延伸免费苹果的背包数组，g 表示不可以再向下延伸免费苹果的背包数组，则对于 u 及其子节点 v，f_u \otimes f_v\to g_u，f_u\otimes g_v\to g_u，g_u\otimes g_v \to g_u。很遗憾，如果用树上依赖性背包，我们会发现上面三种转移无法合并，必须向下递归三个子问题。也就是说，每层将凭空多出来一个背包数组。这个方法行不通。

换种角度，想象一棵树，每个儿子按访问顺序从左到右排列，则从根到叶子的路径将整棵树劈成两半，左边和右边时间戳分别连续。对于中间有特殊部分的问题，套路地维护前后缀再合并。又因为树上依赖背包可以算出每个时间戳前缀的答案，所以可行。

因此，设 f_i 表示考虑到时间戳前缀 i 的答案，满足时间戳为 i 的节点 rev_i 到根的路径上所有节点还没有被加入背包。g_i 同理表示后缀。求出 f, g 后枚举每个节点 i，则相当于合并 f_{dfn_i}，g_{dfn_i} 和 i 到根上所有节点 j 在 a_j 减掉 1 之后的背包 h_i，得到一个大背包 K，则 K_k 加上 i 到根上所有节点的 v 之和的最大值即为答案。

这样还是不太行，因为 K_k 需要 k ^ 2 的时间。考虑将 h 巧妙地融合到 f 或 g 当中，发现设 f_i 满足 rev_i 到根的路径上所有节点 j 暂时只考虑了 a_j - 1 个苹果，且这 a_j - 1 个苹果不强制至少选一个，即可满足条件。也就是说，进入 j 时只不强制必须选地加入 a_j - 1 个苹果，回溯时再强制加入最后一个苹果。

单调队列优化多重背包，时间复杂度 \mathcal{O}(nk)。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using uint = unsigned int;
// using lll = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
inline ll read() {
  ll x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(ll x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 2e4 + 5;
constexpr int K = 5e5 + 5;
int n, k, fa[N], a[N], v[N], s[N];
int ans, hd, tl, d[K], val[K];
vector<int> e[N], f[N], g[N];
void dfs1(int id) {
  s[id] = s[fa[id]] + v[id];
  hd = 1, tl = 0;
  for(int i = 0; i <= k; i++) {
    int c = f[id][i] - i * v[id];
    while(hd <= tl && c >= val[tl]) tl--;
    d[++tl] = i, val[tl] = c;
    while(hd <= tl && d[hd] <= i - a[id]) hd++;
    f[id][i] = val[hd] + i * v[id];
  }
  g[id] = f[id];
  for(int it : e[id]) {
    f[it] = f[id], dfs1(it);
    for(int i = 0; i <= k; i++) f[id][i] = max(f[id][i], f[it][i]);
  }
  for(int i = k; i; i--) f[id][i] = f[id][i - 1] + v[id];
}
void dfs2(int id) {
  for(int i = 0; i <= k; i++) ans = max(ans, f[id][i] + g[id][k - i] + s[id]);
  for(int it : e[id]) {
    f[it] = f[id], dfs2(it);
    for(int i = 0; i <= k; i++) f[id][i] = max(f[id][i], f[it][i]);
  }
  d[hd = tl = 0] = 0, val[0] = 0;
  for(int i = 1; i <= k; i++) {
    int c = f[id][i] - i * v[id];
    while(hd <= tl && d[hd] < i - a[id]) hd++;
    f[id][i] = val[hd] + i * v[id];
    while(hd <= tl && c >= val[tl]) tl--;
    d[++tl] = i, val[tl] = c;
  }
  f[id][0] = 0;
}
void solve() {
  cin >> n >> k, ans = 0;
  for(int i = 1; i <= n; i++) {
    cin >> fa[i] >> a[i] >> v[i];
    e[fa[i]].push_back(i);
  }
  for(int i = 1; i <= n; i++) f[i].resize(k + 1), g[i].resize(k + 1);
  dfs1(1);
  for(int i = 1; i <= n; i++) reverse(e[i].begin(), e[i].end());
  for(int i = 1; i <= n; i++)
    for(int j = 0; j <= k; j++)
      f[i][j] = 0;
  dfs2(1), cout << ans << "\n";
  for(int i = 1; i <= n; i++) {
    e[i].clear();
    vector<int> ().swap(f[i]);
    vector<int> ().swap(g[i]);
  }
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T;
  cin >> T;
  while(T--) solve();
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/10/2
author: Alex_Wei
start coding at 6:25
finish debugging at 9:00
*/