[集训队互测 2025] 火花

[集训队互测 2025] 火花

给定一个 \(n\) 个点的有根树，根为 \(1\)。第 \(i\) 个点上有 \(c_i\) 个物品，价值均为 \(v_i\)。
进行如下两步后，求选出的物品价值最大值：

• 选择 \(t\) 个不同的点，对于每个点，选择它的所有祖先上的物品。
  • 本题保证 \(\boldsymbol{t < c_i}\)，因此不会存在没有物品可取的情况。
• 接下来，还能再选择至多 \(k\) 个物品，但要求在这一步中所选了物品的点是原树的一个连通块。

\(t\) 是给定值，\(1 \leq n, k \leq 10^4\)，\(0\leq t \leq n\)，\(\boldsymbol{t \lt c_i} \leq 10^9\)，\(1\leq v_i \leq 10^9\)，\(\mathrm{fa}_i \lt i\)，\(nk(t+1)\leq 10^7\)。

借鉴了足量的题解。sparkle 题目就该看 spdarkle 题解。

\(t=0\) 时，该问题退化为经典树上依赖背包问题

树上的依赖关系体现为，一个节点不选，则其子树全不选。

将关系转变为 dfn 序，如果一个节点 \(u\) 不选，则直接跳过一整棵子树，即 \(\mathrm{dfn} \gets \mathrm{dfn}+\mathrm{size}_u\)。

定义 dp：\(f_{u,i}\) 表示考虑 dfn 序从 \(1 \sim u\) 的节点选出 \(i\) 个物品。转移是容易的：

\[\begin{aligned} f_{u,i} +p \times v_u &\to f_{u+1,i+p}\quad p \in[1,\min(k-i,c_u)]\\ f_{u,i} &\to f_{u+sz_u,i} \end{aligned} \]

第一类转移使用多重背包的单调队列优化是简单的，做到 \(O(nk)\)。

\(t>0\) 时，状态的记录不足以进行转移

假设 \(g_{i} = 0/1\) 表示 \(i\) 在第一步中是否被选。计算 \(h_u=\displaystyle\sum _{v \in \mathrm{subtree}(u)} g_v\)，如果在进行 \(f_u\) 的转移时，能够在状态中得到 \(h_u\)，就可以简单转移。只需满足 \(h_u+p \le c_i\) 即可，\(p\) 为第二步选的物品数量。

可是如果仅仅将其加入状态中，即令 \(f_{u,i,j}\) 表示……，且 \(h_u=j\)。这样的确可以转移了：

• 进行两步合并，分别合并 \(j=h_u=\sum h_v\) 和 \(i\) 即可，最后再讨论 \(g_u=0/1\)。

复杂度有点高。

考虑 \(t=0\) 时的转移，\(\mathrm{dfn} \gets \mathrm{dfn}+\mathrm{size}_u\) 即为跳过一整棵子树，那么 \(\mathrm{dfn}_u+\mathrm{size}_u\) 处的决策实际上是决定是否往 \(u\) 中走，如果前面的 dp 告诉我直接跳过 \(u\) 价值更大，就直接跳过，否则选择进入 \(u\) 子树。当到了 \(\mathrm{dfn}_u+\mathrm{size}_u\) 时，实际上前面已经算了走/不走 \(u\) 子树的分别的价值。

也就是说，转移是通过试探性地进入子树 \(u\) 计算价值，再与不进入子树 \(u\) 的情况计算的价值相比较来决策的。

所以，转移 \(u\) 的时候分为了两个阶段：

• 计算两种情况分别的价值：强制使 \(u\) 至少选一个数，进入 \(u\) 子树；不进入 \(u\) 子树。
• 在往后转移前，决定一下是否进入 \(u\) 子树。

这意味着进入和回溯时，都需要进行 \(u\) 的决策。把它拍到序列上，容易发现这是欧拉序，可以记 \((\ell_u,r_u)\) 分别为进入和回溯时间。问题是我在 \(x=\ell_u\) 时，并不知道 \(h_u\)（\(h_u\) 无法直接放在状态中，否则离开子树时 \(\mathrm{fa}_u\) 的 \(h\) 是不知道的）。

考虑把 \(h_u\) 给拆了，记录一个 \(g\) 的前缀和，定义 \(f_{u,i,j}\) 表示……，且前面 \(1\sim i-1\)的 \(g\) 之和为 \(j\)。

显然这样我就可以通过进入子树前 \(g\) 之和 \(pre\) 与离开子树时的 \(g\) 之和 \(suf\) 计算出子树内 \(g\) 之和 \(h_u\)，\(h_u=suf-pre\)。于是第二次选的时候，只能选 \([0,c_u-suf+pre]\) 个物品。题目告诉我们 \(suf\le t<c_u\)，所以这个可以分两次选：\([0,pre]\) 和 \([0,c_u-suf]\)。

讨论 dp 转移，设欧拉序列为 \(e_i\)，点 \(u\) 的进入与回溯时间分别为 \(\ell_i,r_i\)。设 \(f_{i,j,p}\) 表示考虑到欧拉序列的第 \(i\) 个数，选了 \(j\) 个数，前面已考虑 \(g\) 取值的点的 \(g\) 之和为 \(p\)。

• \(i=\ell_{e_i}\)，这是进入时间：

  应该干什么呢？🤔

  • 选物品，数量必须在 \([0,p]\) 之间（对应 \([0,pre]\)，强制至少选一个的决定在后面做，因为 \(p\) 不一定大于 \(0\)）：
    \[f_{i,j,p} +xv_{e_i}\to f_{i+1,j+x,p}\quad x\in[0,p] \]

  • 不选物品，整棵子树都得跳过，但还得枚举这棵子树的 \(g\) 之和。
    \[f_{i,j,p}+g_{e_i,x}\to f_{r_{e_i},j,p+x} \quad x \in [0,t-p] \]
    其中 \(g_{e_i,x}\) 表示 \(e_i\) 子树内点 \(v\) 到根路径价值之和 \(s_v\) 的前 \(x\) 大的值之和（一个显然的贪心）。

• \(i=r_{e_i}\)，这是回溯时间：

  应该干什么呢？🤔

  选物品，数量必须在 \([1,c_{e_i}-p]\) 之间（对应 \([0,c_u-suf]\)，但是必须强制选一个）：

  • 使 \(g_{e_i}=0\)：

  \[f_{i,j,p} +xv_{e_i}\to f_{i+1,j+x,p}\quad x\in[1,c_{e_i}-p] \]

  • 使 \(g_{e_i}=1\)：

  \[f_{i,j,p}+xv_{e_i}+s_{e_i}\to f_{r_{e_i},j+x,p+1} \quad x \in [1,c_{e_i}-p) \]

这里面的转移有 \(3\) 个都是多重背包形式，固定 \(p\)，用单调队列就能做到 \(\mathcal O(nkt)\)。

剩下的 \(1\) 个转移：

\[f_{i,j,p}+g_{e_i,x}\to f_{r_{e_i},j,p+x} \quad x \in [0,t-p] \]

\(g_{e_i,x}\) 显然是凸的，固定 \(u=e_i\)，可以处理 \(f_{\ell_u} \to f_{r_u}\) 的转移（\((\max,+)\) 卷积，单 Convex，分治转移）。剩下的都不是难点。