题解：树上取苹果的最大幸福度

问题转化

给定一棵以 $1$ 为根的树，每个节点 $i$ 有 $a_i$ 个苹果，每个苹果价值 $v_i$。取苹果规则：

1. 如果在节点 $i$ 取了至少一个苹果，则必须在其父节点也取至少一个苹果。
2. 设总共取了 $t$ 个苹果，取了苹果的节点的最大深度为 $h$（根深度为 $1$），要求 $t - h \le k$。

目标：最大化总价值。

关键观察

1. 深度与取苹果的关系

令取了苹果的节点集合为 $S$，$S$ 非空。设 $d_{\max} = \max_{i \in S} depth(i)$，则 $h = d_{\max}$。

条件 $t - h \le k$ 可写为 $t \le h + k$，其中 $t = \sum_{i \in S} x_i$，$x_i$ 是在节点 $i$ 取的苹果数，$1 \le x_i \le a_i$。

2. 规则1的传递性

规则1意味着：如果节点 $i$ 取了苹果，则从 $i$ 到根的整条路径上的每个节点都必须取至少一个苹果。

因此，$S$ 必须是一个包含根节点的连通子图（到根的路径连通）。

设 $S$ 是某个深度 $h$ 的节点为最深节点的连通块（包含根），则所有节点 $i \in S$ 必须取 $x_i \ge 1$，且 $S$ 外的节点不能取苹果。

3. 问题转化为选择深度和连通块

枚举最深深度 $h$（$1 \le h \le$ 树高），选择以某个深度为 $h$ 的节点 $u$ 为最深节点的连通块 $S$（包含根到 $u$ 的路径上的所有节点），并在 $S$ 内取苹果，满足 $\sum_{i \in S} x_i \le h + k$，最大化 $\sum_{i \in S} x_i v_i$。

由于 $v_i > 0$，我们希望在不超过总数限制的情况下，尽量多取苹果，且优先取 $v_i$ 大的苹果。

4. 转化为背包问题

对于固定的连通块 $S$，问题变为：每个节点 $i \in S$ 有 $a_i$ 个物品，每个物品价值 $v_i$，体积为 $1$，总容量 $C = h + k$，且每个节点至少选 $1$ 个物品（因为取了至少一个苹果）。

设 $b_i = a_i - 1 \ge 0$ 表示额外可以多取的苹果数（已经取了至少 $1$ 个），则问题变为：

• 首先每个节点取 $1$ 个苹果，基础价值 $sumV = \sum_{i \in S} v_i$，已用体积 $|S|$。
• 剩余容量 $C' = (h + k) - |S|$，每个节点最多再取 $b_i$ 个苹果，每个苹果价值 $v_i$。
• 在容量 $C'$ 内，从所有节点中选择若干额外苹果，最大化总价值。

这是经典的分组背包：每组是节点 $i$，有 $b_i$ 个相同价值 $v_i$ 的物品（体积均为 $1$），最多选 $b_i$ 个。

5. 贪心选择

由于每组内物品价值相同，最优策略是优先选择价值 $v_i$ 大的节点多取苹果。

因此，对于固定的 $S$，将所有节点按 $v_i$ 降序排序，然后贪心取前若干大的 $v_i$ 的额外苹果，直到达到容量 $C'$ 或没有额外苹果可拿。

6. 枚举连通块

树高可能较大，但 $k$ 可达 $5\times 10^5$，$n \le 20000$。

直接枚举每个节点 $u$ 作为最深节点，其连通块 $S$ 就是根到 $u$ 的路径上的所有节点。
设 $P(u)$ 表示根到 $u$ 的路径节点集合，$|P(u)| = depth(u)$。

则 $h = depth(u)$，容量 $C = depth(u) + k$，基础占用体积 $depth(u)$，剩余容量 $C' = k$。

因此，剩余容量只与 $k$ 有关，与 $u$ 无关！
因为 $C' = (depth(u) + k) - depth(u) = k$。

所以对于任意节点 $u$，可额外取的苹果数不超过 $k$。

7. 统一问题

现在问题简化为：
对于每个节点 $u$，取根到 $u$ 路径上所有节点至少一个苹果（基础价值 $sumV(u) = \sum_{i \in P(u)} v_i$），然后还可以额外取最多 $k$ 个苹果（从路径上的节点取，每个节点 $i$ 最多额外取 $a_i - 1$ 个，每个价值 $v_i$），最大化总价值。

总价值 = $sumV(u)$ + 从 $P(u)$ 中贪心选最多 $k$ 个额外苹果的最大价值。

8. 转化为树上问题

我们需要对每个节点 $u$ 计算：

$$ans(u) = sumV(u) + \text{greedy}(P(u), k)$$

其中 $\text{greedy}(P(u), k)$ 表示从 $P(u)$ 中选最多 $k$ 个额外苹果（节点 $i$ 最多 $a_i-1$ 个）的最大价值。

由于 $v_i$ 都为正，贪心就是取 $v_i$ 最大的那些苹果。

9. 维护路径上的价值前 $k$ 大苹果

对于每个节点 $u$，需要知道根到 $u$ 路径上所有节点的 $(v_i, b_i)$ 对，并从中选出最多 $k$ 个价值最大的苹果。

由于 $k$ 很大（可达 $5\times 10^5$），但 $n \le 20000$，$v_i \le 100$，$b_i$ 可能很大（$a_i$ 可达 $10^8$），但实际额外苹果数受 $k$ 限制。

我们可以按 $v_i$ 值（$1$ 到 $100$）分组。对每个 $v$，统计路径上 $v_i = v$ 的节点的额外苹果总数 $cnt_v$。

贪心时，从 $v=100$ 向下取，每次取 $min(cnt_v, remaining)$ 个价值 $v$ 的苹果。

10. 树上前缀和

设 $pre_v[u]$ 表示根到 $u$ 路径上 $v_i = v$ 的节点的额外苹果总数 $b_i$ 之和。

则对节点 $u$，$cnt_v = pre_v[u]$。

那么 $\text{greedy}(P(u), k) = \sum_{v=100}^{1} v \times \min(pre_v[u], rem)$，其中 $rem$ 是剩余可取的苹果数，初始 $rem=k$，每次减去已取的。

11. 计算答案

对每个节点 $u$：

1. 计算 $sumV(u)$（根到 $u$ 路径上 $v_i$ 之和）。
2. 计算 $pre_v[u]$ 对所有 $v=1..100$。
3. 贪心取额外苹果：
   $rem = k$, $extra = 0$
   从 $v=100$ 到 $1$：
   $take = \min(pre_v[u], rem)$
   $extra += v \times take$
   $rem -= take$
4. $ans(u) = sumV(u) + extra$
5. 最终答案 = $\max_{u} ans(u)$

12. 预处理前缀和

DFS 遍历树，维护当前路径上的 $sumV$ 和 $pre_v$ 数组。

由于 $v_i \le 100$，$pre_v$ 只有 $100$ 个值，可以 $O(100)$ 更新。

复杂度：$O(n \times 100)$ 预处理，$O(n \times 100)$ 计算每个节点的贪心（因为每次从 $100$ 到 $1$ 扫描）。

总复杂度 $O(100n)$，可过。

13. 处理大 $b_i$

$b_i = a_i - 1$ 可能很大（$10^8$），但 $k \le 5\times 10^5$，所以实际最多取 $k$ 个额外苹果。
在统计 $pre_v[u]$ 时，如果 $b_i > k$，可以截断为 $k$，因为再多也无用。

因此令 $b'_i = \min(b_i, k)$，再累加到 $pre_v[u]$ 中。

但注意 $pre_v[u]$ 是多个节点的 $b'_i$ 之和，可能超过 $k$，所以贪心取 $min(pre_v[u], rem)$ 即可。

14. 算法步骤

1. 读入 $Q$，对每组数据：
   • 读入 $n, k$ 和树结构。
   • 对每个节点 $i$，计算 $b_i = \min(a_i - 1, k)$（如果 $a_i=0$ 则不能取，但题目保证 $a_i>0$）。
2. DFS 从根开始：
   • 维护当前路径的 $sumV$ 和数组 $pre[1..100]$。
   • 进入节点 $u$ 时，更新： $sumV += v_u$ $pre[v_u] += b_u$
   • 计算当前节点的答案 $ans(u)$： $rem = k$, $extra = 0$ 从 $v=100$ 到 $1$： $take = \min(pre[v], rem)$ $extra += v \times take$ $rem -= take$ $ans(u) = sumV + extra$ 更新全局最大值。
   • 递归子节点。
   • 回溯时恢复 $sumV$ 和 $pre[v_u]$。
3. 输出全局最大值。

15. 注意

• 根节点必须取至少一个苹果（因为如果取任何苹果，根必须取）。
• 如果 $k=0$，则只能取路径上的基础苹果（每个节点恰好取 $1$ 个）。
• 答案可能超过 $32$ 位整数，用 $64$ 位存储。

复杂度分析

• 每组数据：$O(100n)$
• $n \le 20000$，$Q \le 5$，总操作约 $1000$ 万次，可过。