题解：矿坑开采最优规划

问题分析

我们有一个二叉树结构的矿坑，需要按顺序执行 $q$ 个计划。每个计划有四个阶段，其中执行阶段有四种类型：

1. 机器人向浅移动
2. 机器人向深移动
3. 送入人类
4. 移出人类

目标是在满足移动约束的前提下，最大化所有计划开采阶段的总产出。

---

1. 关键观察

移动规则的核心限制：

• 每个节点只能有一个工人
• 每个通道同时只能有一个人通过
• 这意味着人类的移动是受限的，不能"穿过"其他工人

二叉树性质：

由于是二叉树且 $f_i < i$，我们可以建立明确的父子关系，便于DP设计。

---

2. 状态设计

这是一个复杂的动态规划问题，需要记录：

• 机器人当前位置
• 人类的位置分布
• 当前计划编号

但由于 $n \leq 301$, $q \leq 600$，直接记录所有人类位置不可行。

---

3. 重要简化

观察发现：在开采阶段，只有机器人所在位置和有人类的节点影响产出。

由于人类可以在准备/调整阶段任意移动（满足通道限制），对于固定的机器人位置，我们可以独立计算最优的人类分布。

---

4. 预处理收益

对于每个节点 $u$（机器人位置）和人类位置集合 $S$，开采收益为：

$$\text{profit}(u, S) = r_u + \sum_{v \in S, v \neq 1} p_v $$

其中 $r_u = 0$ 当 $u = 1$（地面无产出）。

但 $S$ 的取值太多，需要进一步简化。

---

5. 人类移动的可行性

由于通道限制，人类的位置分布必须满足：从根到每个有人类的节点的路径上不能有其他人类。

实际上，这等价于：人类的位置构成一个反链（antichain），即任意两个人类节点没有祖先-后代关系。

---

6. 状态定义

设 $dp[i][u][h]$ 表示执行完前 $i$ 个计划，机器人在节点 $u$，矿坑内有 $h$ 个人类时的最大总收益。

但这样缺少人类位置信息，无法计算收益。

---

7. 关键突破：分离计算

我们可以将问题分解：

1. 机器人移动规划：确定机器人在每个计划后的位置
2. 人类分配优化：对于固定的机器人路径，分配人类到最优位置

对于固定的机器人位置序列 $pos[0..q]$，其中 $pos[0] = s$，最大总收益为：

$$\sum_{i=1}^q \max_{S_i \subseteq V} \left( r_{pos[i]} + \sum_{v \in S_i} p_v \right) $$

满足：

• $|S_i| = h_i$（$h_i$ 是第 $i$ 个计划后的人类数量）
• $S_i$ 是反链
• 人类数量 $h_i$ 变化受类型3/4计划约束

---

8. 人类数量变化

设 $H[i]$ 表示第 $i$ 个计划后的人类数量：

• 初始 $H[0] = 0$
• 类型3：$H[i] = H[i-1] + 1$
• 类型4：$H[i] = H[i-1] - 1$
• 类型1/2：$H[i] = H[i-1]$

类型3要求 $1$ 号点无人，类型4要求 $1$ 号点有人。

---

9. 反链的最大权重和

对于固定数量 $h$，在二叉树中找到权重最大的 $h$-反链是经典问题。

设 $f[u][h]$ 表示以 $u$ 为根的子树中，选择 $h$ 个节点形成反链的最大权重和。

转移：

• 不选 $u$：$f[u][h] = \max_{a+b=h} (f[l][a] + f[r][b])$
• 选 $u$：$f[u][h] = p_u + \max_{a+b=h-1} (f[l][a] + f[r][b])$，且 $a,b$ 可以来自空集

其中 $l, r$ 是 $u$ 的左右儿子。

---

10. 完整算法框架

步骤1：预处理子树DP

对每个节点 $u$，计算 $f[u][0..n]$，表示 $u$ 子树中选 $k$ 个节点的最大反链权重。

步骤2：枚举机器人路径

由于 $n \leq 301, q \leq 600$，直接枚举所有路径不可行。需要用DP：

设 $dp[i][u]$ 表示执行完前 $i$ 个计划，机器人在 $u$ 的最大收益。

转移：

• 类型1：$dp[i][u] = \max_{v \in \text{ancestors}(u)} dp[i-1][v] + \text{best_profit}(u, H[i])$
• 类型2：$dp[i][u] = \max_{v \in \text{descendants}(u)} dp[i-1][v] + \text{best_profit}(u, H[i])$
• 类型3/4：$dp[i][u] = dp[i-1][u] + \text{best_profit}(u, H[i])$

其中 \text{best_profit}(u, h) = r_u + f[u][h]（实际上需要全局最优，不只是 $u$ 的子树）

---

11. 全局最优反链

对于全树和固定数量 $h$，最大权重 $h$-反链为 $f[1][h]$。

因此：

\text{best_profit}(u, h) = r_u + f[1][h]

但要注意：当机器人在 $u$ 时，$u$ 上不能有人类。所以需要调整：

实际收益 = $r_u +$（全树选 $h$ 个节点的最大反链权重，且不包含 $u$）

设 $g[u][h]$ 表示全树选 $h$ 个节点的最大反链权重，且不选 $u$。

可以通过树形DP计算 $g$。

---

12. 最终DP方程

设 $dp[i][u]$ 表示前 $i$ 个计划后机器人在 $u$ 的最大收益。

则：

$$dp[i][u] = \max_{\text{valid } v} \left( dp[i-1][v] + r_u + g[u][H[i]] \right) $$

其中 $v$ 的选取：

• 类型1：$v$ 是 $u$ 的祖先，且 $v \neq u$（至少移动一步）
• 类型2：$v$ 是 $u$ 的后代，且 $v \neq u$
• 类型3/4：$v = u$

初始 $dp[0][s] = 0$，其他 $-\infty$。

答案 = $\max_u dp[q][u]$。

---

13. 预处理 $g$ 数组

$g[u][h]$ 的计算：

对于根节点 $1$：

• $g[1][h] = f[1][h]$（根可选可不选）

对于其他节点 $u$，设父节点为 $p$：

• 不选 $u$：$g[u][h] = \max_{a+b+c=h} (f[l][a] + f[r][b] + g[p][c])$
• 但这样复杂度太高

实际上，我们可以用包含-排除思想：

$$g[u][h] = \max_{0 \le k \le h} (f[1][k] - f[u][h-k]) $$

但这不是精确的。

更精确的方法：对每个 $u$，做一次树形DP，强制不选 $u$。

---

14. 复杂度优化

由于 $n \leq 301$，我们可以对每个节点 $u$ 预处理 $g[u][0..n]$。

总复杂度：

• 预处理 $f$：$O(n^3)$
• 预处理 $g$：$O(n^4)$，但可以优化到 $O(n^3)$
• 主DP：$O(q \cdot n^2)$

在给定数据范围内可行。

---

15. 实现细节

树形DP求 $f$：

void dfs_f(int u) {
    vector<int> temp(n+1, -INF);
    temp[0] = 0;
    
    for (int v : children[u]) {
        dfs_f(v);
        vector<int> new_temp(n+1, -INF);
        for (int a = 0; a <= n; a++) {
            if (temp[a] < 0) continue;
            for (int b = 0; a+b <= n; b++) {
                if (f[v][b] < 0) continue;
                new_temp[a+b] = max(new_temp[a+b], temp[a] + f[v][b]);
            }
        }
        temp = new_temp;
    }
    
    // 不选u
    for (int h = 0; h <= n; h++) {
        f[u][h] = temp[h];
    }
    // 选u
    for (int h = 1; h <= n; h++) {
        f[u][h] = max(f[u][h], p[u] + temp[h-1]);
    }
}

主DP：

// 初始化
vector<vector<ll>> dp(q+1, vector<ll>(n+1, -INF));
dp[0][s] = 0;

// 计算人类数量序列H
vector<int> H(q+1);
H[0] = 0;
for (int i = 1; i <= q; i++) {
    if (op[i] == 3) H[i] = H[i-1] + 1;
    else if (op[i] == 4) H[i] = H[i-1] - 1;
    else H[i] = H[i-1];
}

// DP转移
for (int i = 1; i <= q; i++) {
    for (int u = 1; u <= n; u++) {
        if (dp[i-1][u] < 0) continue;
        
        if (op[i] == 1) {
            // 向浅移动
            for (int v : get_ancestors(u)) {
                if (v == u) continue;  // 至少移动一步
                dp[i][v] = max(dp[i][v], dp[i-1][u] + r[v] + g[v][H[i]]);
            }
        } else if (op[i] == 2) {
            // 向深移动
            for (int v : get_descendants(u)) {
                if (v == u) continue;
                dp[i][v] = max(dp[i][v], dp[i-1][u] + r[v] + g[v][H[i]]);
            }
        } else {
            // 类型3或4，机器人不动
            dp[i][u] = max(dp[i][u], dp[i-1][u] + r[u] + g[u][H[i]]);
        }
    }
}

---

16. 边界情况处理

• 类型3时检查 $1$ 号点是否无人
• 类型4时检查 $1$ 号点是否有人
• 人类数量 $H[i]$ 不能为负
• 如果任何 $dp[i][u]$ 都无解，输出 No solution.

---

总结

本题的关键在于：

1. 将问题分解为机器人路径规划和人类分配两个子问题
2. 利用反链性质简化人类位置约束
3. 设计树形DP计算最优人类分布
4. 结合机器人移动约束进行动态规划

这是一个复杂的树形动态规划问题，考察对树结构和约束优化的综合处理能力。