题目链接：「THUPC 2024 初赛」采矿 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 「THUPC 2024 初赛」采矿 题解 题意简述 给定一棵二叉树，根节点为 1（地面，无产出）。每个非根节点 i 有： * 机器人产出 r[i]（当机器人位于该节点时每单位时间产出） * 人类产出 p[i]（当人类位于该节点时每单位时间产出） 初始时，机器人位于节点 s，矿坑内没有人类工人。 所有节点和通道容量均为 1，即每个节点/通道同一时刻只能容纳一名工人（包括机器人和人类）。 共有 q 条计划按顺序执行，每条计划类型为： * 1：机器人向更浅（父节点）方向移动至少一条边； * 2：机器人向更深（子节点）方向移动至少一条边； * 3：从 1 号节点进入一名人类（即增加一个人类工人）； * 4：从 1 号节点移出一名人类（即减少一个人类工人）。 在每两条计划之间，人类可以任意移动（但不能进出矿坑），机器人不能移动。每条计划执行时，先调整人类位置（准备阶段），然后执行操作（机器人移动或人类进出），再调整人类位置（调整阶段），最后开采一单位时间，所有有工人的非地面节点按照对应工人的产出值贡献收益。 要求执行完所有计划后，总收益最大，若某次操作无法进行（例如移出人类时 1 号节点无人类，或机器人移动无路可走），输出 No solution.。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 核心转化 1. 固定人类总数 操作 3 和 4 只改变矿坑内的人类总数，记作 cnt。在两次操作之间，人类可以任意重排，只要满足每个节点容量为 1（包括机器人所在节点不能有人类）。 2. 状态设计 由于人类可以任意移动，我们只需要关心机器人的位置以及左右子树中的人类数量即可确定当前状态下的最大可能收益。 设状态为 dp[u][l][r]，表示： * 机器人当前位于节点 u； * 在 u 的左子树中有 l 个人类； * 在 u 的右子树中有 r 个人类； * 其余 cnt - l - r 个人类位于 u 子树以外的节点。 由于人类总数固定为 cnt，且 u 的左右子树大小已知，l 和 r 的取值范围有上下界。 3. 收益计算 当机器人位于 u 时，收益由四部分组成： * 机器人本身的产出：a[u]（即 r[u]）； * 左子树中 l 个人类：为了最大化收益，应选择左子树中 p 值最大的 l 个节点； * 右子树中 r 个人类：选择右子树中 p 值最大的 r 个节点； * 其他区域中 cnt - l - r 个人类：选择除 u 的整棵子树外的所有节点中 p 值最大的 cnt - l - r 个节点。 因此我们需要预处理： * sum1[u][k]：u 的子树内所有节点（不包括 u？但代码中包含了 b[u]）中 p 值最大的前 k 个之和（按降序排列）； * sum2[u][k]：除 u 的子树外的所有节点中 p 值最大的前 k 个之和。 这样可以在 O(1) 时间内计算任意状态的收益。 4. 操作转移 操作 1：机器人向上移动 机器人从 u 移动到其父节点 f。设 u 是 f 的左儿子（右儿子情况对称）。 在移动前，机器人位于 u，左子树人数为 l，右子树人数为 r。整个 u 子树内总人数为 lr = l + r。移动后，机器人位于 f，此时 u 子树（即 f 的左子树）内人数仍为 lr，而 f 的右子树以及其他区域的人数需要重新分配。 由于人类可以任意移动，我们只需要知道 f 的左子树人数为 lr，右子树人数为 c，其中 c 可取 0 到 min(cnt - lr, sz[right]) 之间的任意值。因此转移为： 其中 lr = l + r。 实际代码中，先对每个节点 u 计算 mx[lr] = max_{l+r=lr} (max(dp[u][l][r], g[u][l][r]))，然后一次性更新父节点。 操作 2：机器人向下移动 机器人从 u 移动到其某个子节点 v（左或右）。 若移动到左儿子 v，则原来 u 的左子树中部分人数留在左子树，部分可能分配给其他区域（因为机器人离开 u 后，u 本身空出，可以容纳一个人，但 u 是机器人原来的位置，现在机器人走了，但人类可以进入 u，但人类数量是固定的，我们不需要显式移动，只需重新分配）。转移时，枚举 v 的左子树人数 l2 和右子树人数 r2，它们之和等于原来 u 的左子树总人数 l（因为整个左子树现在被 v 继承？实际上，v 是 u 的左儿子，所以 u 的左子树包含 v 及其整棵子树。当机器人从 u 移动到 v 时，v 的左子树和右子树仍然属于 u 的左子树区域，因此原来 u 的左子树总人数 l 现在被分配到 v 的左右子树中。而 u 的右子树人数 r 保持不变，仍属于 u 的右子树，但现在 u 的右子树在机器人移动后属于“其他区域”（因为机器人不在 u 了，u 的子树外区域包含了 u 的右子树和更上层）。但我们在状态中，dp[v][l2][r2] 的“其他区域”指的是 v 子树外的区域，而 u 的右子树和上层节点都属于这些“其他区域”。所以转移时，我们需要将原来 u 的右子树人数 r 并入“其他区域”中，而原“其他区域”人数是 cnt - l - r，现在 v 的子树外区域人数为 cnt - (l2 + r2)，它包含了原来的 r 以及原来的其他区域人数。 因此转移为： 其中 l2 + r2 = l（左子树人数不变），r 被并入其他区域，无需显式处理，只要总数匹配即可。 代码中通过枚举 l（即 v 子树内总人数）并计算 mx[l]，然后更新子节点。 5. 无解判断 在执行过程中，若 cnt 变为负数或超过 n-1（因为机器人占一个节点），则无解。另外，若操作 1 或 2 时机器人无法移动（如已在根节点或没有子节点），则也无法完成，但代码中未显式检查，因为转移时若无可达状态，最终答案会为 -INF，输出 No solution.。 6. 最终答案 执行完所有计划后，枚举所有可能的机器人位置和左右子树人数，取最大收益。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 复杂度分析 * 状态数：节点数 n × 左子树大小 × 右子树大小。由于二叉树特性，总状态数为 O(n^3)，但实际中 n ≤ 300，可接受。 * 预处理：每个节点排序子树内外 p 值，总复杂度 O(n^2 log n)。 * 转移：向上和向下各需 O(n^3)，总复杂度约为 O(n^3 + q * n^3)，但通过优化（如 mx 数组）可在 n=300 时通过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ CODE