魔塔问题 C++ 题解

核心思路

本题核心是 树形动态规划（树形DP） 结合 贪心排序，利用树的依赖关系和防御值单调递增特性，通过线性伤害模型优化子树处理顺序，最小化总伤害。

关键观察

1. 树的依赖关系：处理子树必须先处理父节点（父节点是连接根与子树的唯一路径，需先变为空地）。
2. 线性伤害模型：每个怪物的伤害可表示为 $K_m \times (a - D')$（$K_m = \lceil \frac{h}{A-d} \rceil - 1$，$D'$ 为处理时的防御值），子树总伤害是关于初始防御的线性函数 $f(D) = C + K \times D$（$C$ 为常数项，$K$ 为系数）。
3. 子树排序贪心：子树处理顺序影响总伤害，最优顺序由子树的「宝石总加成 $s$」和「伤害系数 $K$」决定，排序条件为：子树 $a$ 应在子树 $b$ 前处理，当且仅当 $b.K \times a.s \leq a.K \times b.s$（最小化交叉项伤害）。

动态规划状态定义

对每个节点 $u$，维护三个参数：

• $C_u$：处理 $u$ 及其子树的总伤害常数项（与初始防御无关）；
• $K_u$：处理 $u$ 及其子树的总伤害系数（与初始防御相乘）；
• $s_u$：$u$ 及其子树的总防御加成（宝石总和）。

状态转移

1. 节点本身处理：
   • 宝石节点（opt=1）：无伤害，$C_0=0$，$K_0=0$，$s_0=v_i$；
   • 怪物节点（opt=2）：计算 $K_m = \lceil \frac{h_i}{A-d_i} \rceil - 1$，$C_0=K_m \times a_i$，$K_0=-K_m$，$s_0=0$。
2. 子树处理：
   • 收集子节点的 $(C_v, K_v, s_v)$，按贪心条件排序；
   • 计算子树总常数项 $\text{sum}_C$、总系数 $\text{sum}_K$、总防御加成 $\text{sum}_s$ 和交叉项 $\text{cross}$（子树顺序带来的额外伤害）；
   • 合并得到节点 $u$ 的参数：$$C_u = C_0 + \text{sum}_C + \text{cross}$$ $$K_u = K_0 + \text{sum}_K$$ $$s_u = s_0 + \text{sum}_s$$
3. 最终答案：根节点（1号点）的总伤害为 $C_1 + K_1 \times D$（初始防御为 $D$）。

C++ 代码实现

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 3e5 + 5;

vector<vector<int>> adj(MAXN);       // 邻接表
vector<vector<int>> children(MAXN);  // 每个节点的子节点列表（有根树）
int parent[MAXN];                    // 父节点标记
int opt[MAXN];                       // 节点类型（1=宝石，2=怪物）
int v[MAXN];                         // 宝石的防御加成
int h[MAXN], a[MAXN], d[MAXN];       // 怪物的属性（生命、攻击、防御）

// DP状态：C=常数项，K=系数，s=总防御加成
struct NodeDP {
    ll C, K, s;
    NodeDP(ll c = 0, ll k = 0, ll s = 0) : C(c), K(k), s(s) {}
};
NodeDP dp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int c;
    cin >> c;
    int n, A, D;
    cin >> n >> A >> D;

    // 读取边，构建邻接表
    for (int i = 0; i < n-1; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    // 读取2~n号节点的属性
    for (int u = 2; u <= n; ++u) {
        cin >> opt[u];
        if (opt[u] == 1) {
            cin >> v[u];
        } else {
            cin >> h[u] >> a[u] >> d[u];
        }
    }

    // BFS构建有根树（以1为根），确定父节点和子节点
    fill(parent, parent + n + 1, 0);
    queue<int> q;
    q.push(1);
    parent[1] = -1;  // 根节点无父节点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (parent[v] == 0 && v != parent[u]) {
                parent[v] = u;
                children[u].push_back(v);
                q.push(v);
            }
        }
    }

    // 迭代式后序遍历，计算DP
    stack<pair<int, bool>> st;
    st.push({1, false});
    while (!st.empty()) {
        auto [u, visited] = st.top();
        st.pop();
        if (!visited) {
            // 第一次弹出：标记为已访问，逆序压入子节点（保证后序遍历顺序）
            st.push({u, true});
            for (int i = children[u].size() - 1; i >= 0; --i) {
                st.push({children[u][i], false});
            }
        } else {
            // 第二次弹出：处理当前节点
            ll C0, K0, s0;
            if (u == 1) {
                // 根节点是空地，无属性
                C0 = 0;
                K0 = 0;
                s0 = 0;
            } else if (opt[u] == 1) {
                // 宝石节点
                C0 = 0;
                K0 = 0;
                s0 = v[u];
            } else {
                // 怪物节点：计算K_m和初始C0、K0
                int attack_power = A - d[u];
                ll K_m = (h[u] + attack_power - 1) / attack_power - 1;  // ceil(h/attack_power) - 1
                C0 = K_m * a[u];
                K0 = -K_m;
                s0 = 0;
            }

            // 收集所有子节点的DP状态
            vector<NodeDP> child_dps;
            for (int v : children[u]) {
                child_dps.push_back(dp[v]);
            }

            // 按贪心条件排序子节点：a在b前 iff b.K * a.s <= a.K * b.s
            sort(child_dps.begin(), child_dps.end(), [](const NodeDP& x, const NodeDP& y) {
                return (ll)y.K * x.s <= (ll)x.K * y.s;
            });

            // 计算子树的sum_C、sum_K、prefix_s、cross
            ll sum_C = 0, sum_K = 0, prefix_s = 0, cross = 0;
            for (const auto& nd : child_dps) {
                cross += nd.K * prefix_s;
                sum_C += nd.C;
                sum_K += nd.K;
                prefix_s += nd.s;
            }

            // 合并当前节点和子树的DP状态
            dp[u].C = C0 + sum_C + cross;
            dp[u].K = K0 + sum_K;
            dp[u].s = s0 + prefix_s;
        }
    }

    // 根节点1的总伤害 = C1 + K1 * 初始防御D
    ll total_damage = dp[1].C + dp[1].K * D;
    cout << total_damage << endl;

    return 0;
}

复杂度分析

• 时间复杂度：$O(n \log d)$，其中 $d$ 为节点最大度数。树的总度数为 $2(n-1)$，每个节点的子节点排序时间为 $O(d \log d)$，整体排序总时间为 $O(n \log d)$，其余操作均为线性。
• 空间复杂度：$O(n)$，用于存储邻接表、节点属性、DP状态和栈/队列，可应对 $n=3 \times 10^5$ 的大数据规模。

关键优化点

1. 迭代式后序遍历：避免递归栈溢出，适配大规模数据；
2. 贪心排序：通过子树排序最小化交叉项伤害，是最优解的核心；
3. 线性伤害模型：将子树伤害抽象为线性函数，简化状态合并逻辑；
4. 高效输入输出：关闭同步流，适配大规模输入。