牛半仙的魔塔

形式化题目

魔塔是一棵 $n$ 个点的树，勇士从 1 号点出发（1 号点没有魔物）。勇士有血量 $H$ 、攻击 $A$ 、防御 $D$ 三个属性；点 $i$ （ $i \geqslant 2$ ）上的魔物有血量 $b_i$ 、攻击 $a_i$ 、防御 $d_i$ ，打死后给 $val_i$ 级经验，每升一级勇士防御 $+1$ 。

战斗规则：

勇士先手，双方轮流出手一次造成「攻击 $-$ 自己面对的防御」的伤害，血量 $\leqslant 0$ 的一方死亡；
勇士首次到达某点时立即与该点魔物战斗，魔物死后该点不再刷怪；
树上移动不花代价、不掉血。

由于必须先走到父亲点才能进入子树，合法的战斗顺序恰好是所有父亲先于儿子的排列。问打完全部魔物后的最大剩余血量；若勇士中途死亡则输出 $-1$ （评测数据中不会出现死亡）。

样例： $n = 6$ ，边 $(1,2),(1,3),(1,4),(4,5),(5,6)$ ，勇士 $50000\ 10\ 0$ ，魔物按节点 $2 \sim 6$ 依次为 $(35,54,2,4),(25,55,3,5),(21,51,4,5),(20,64,5,3),(43,64,6,1)$ ，输出 $48901$ 。

下图为样例的树形结构与最优出战顺序：

graph TD
    N1["1 起点"] --> N2["2 第4个打"]
    N1 --> N3["3 第2个打"]
    N1 --> N4["4 第1个打"]
    N4 --> N5["5 第3个打"]
    N5 --> N6["6 第5个打"]

图中给出最优出战顺序 $4 \to 3 \to 5 \to 2 \to 6$ ：它满足「父亲先于儿子」（4 先于 5、5 先于 6），可以证明这就是最优解，推导见下文。

正解

思路

第一步：算清单场战斗的代价。

勇士攻击 $A$ 、魔物防御 $d$ ，打死一只怪要出手 $k = \lceil b/(A-d) \rceil$ 次；因为勇士先手，魔物只来得及反击 $t = k-1$ 次。设交战时勇士防御为 $D$ ，这一场的损失是

\text{loss} = t \cdot (a - D),

打完后防御变成 $D + val$ 。于是「挨打次数 $t$ 」是怪的固有属性，「升级 $val$ 」是收益，每挨一次打换到的升级 $\rho = val / t$ 就是这场战斗的性价比。

第二步：把总血量拆成与顺序有关/无关的两部分。

设战斗按 $i_1, i_2, \dots$ 进行，第 $i$ 场交战时防御 $D_i = D_0 + \sum_{j \text{ 在 } i \text{ 前}} val_j$ ，则

H_{\text{final}} = H - \sum_i t_i a_i + D_0 \sum_i t_i + \underbrace{\sum_{j \text{ 在 } i \text{ 前}} val_j \cdot t_i}_{S}.

前三项都是常数，最大化剩余血量 $\Leftrightarrow$ 最大化 $S$ ：每一只怪的 $val$ 要尽早生效，好让它乘上后面所有怪的 $t$ 。

第三步：朴素做法与瓶颈。

枚举所有「父亲先于儿子」的合法排列逐个算 $S$ ： $n \leqslant 15$ 时勉强可行（对应题面 20% 子任务）， $n$ 到 $10^5$ 时排列数指数爆炸。瓶颈很明确：我们需要一个不用枚举的顺序准则。

第四步：没有树约束时，按性价比排序。

比较紧邻的两场 $i$ 恰好排在 $j$ 前面与反过来： $i$ 在前贡献 $val_i \cdot t_j$ ， $j$ 在前贡献 $val_j \cdot t_i$ 。两者相减得 $val_j t_i - val_i t_j$ ，所以交换后更优 $\Leftrightarrow$ 把 $\rho = val/t$ 大的排前面（相邻交换论证），全按 $\rho$ 从大到小排即最优。

第五步：树约束下的块合并贪心。

父亲必须先打，儿子不能插到父亲前面，所以把「一个点 + 已经并进来的子块」视为一个块，块的性价比是加权平均：

\rho(\text{块}) = \frac{\sum val}{\sum t}.

用大根堆按 $\rho$ 维护所有块，反复弹出全局最大的块：

若块顶的父亲已出战：整块立刻出战——块顶先打，各子块按它们并入的先后（即 $\rho$ 从高到低）依次出战；
若父亲还没上场：把整块并进父亲所在的块（ $\rho$ 取加权平均），相当于先攒着，等父亲能上场时再和别人比性价比。

正确性有两个关键点：

块交换引理：两个互不相干的块 $X、Y$ 相邻时， $X$ 在前的收益是 $\text{Val}_X \cdot t_Y$ ， $Y$ 在前是 $\text{Val}_Y \cdot t_X$ ， $\rho$ 高的整块排前面更优。而每次合并出的新块 $\rho$ 是「刚弹出的最大值」与「父亲块（不超过它）」的加权平均，所以弹出序列单调不增——同一父亲名下的子块天然按 $\rho$ 降序并入，整块出战时内部顺序满足引理 1。
可以交换成贪心形式：任何合法方案中，儿子块都只能排在父亲之后；把尚未上场的父亲块与儿子块捆绑成整体参与性价比比较，不改变它与其他块的相对收益，因此逐块做相邻交换，任意方案都能化成贪心给出的块状方案且 $S$ 不降。

用样例验证公式与顺序： $\rho$ 依次为节点 $3、4$ （ $5/3 \approx 1.67$ ）、节点 $2、5$ （ $1$ ）、节点 $6$ （ $0.1$ ），贪心给出 $4 \to 3 \to 5 \to 2 \to 6$ ，恰好满足父亲先打：

出战	交战前防御 $D$	挨打次数 $t$	每次掉血 $a-D$	本场掉血	剩余血量	战后 $D$
4	0	3	$51-0=51$	153	49847	5
3	5	3	$55-5=50$	150	49697	10
5	10	3	$64-10=54$	162	49535	13
2	13	4	$54-13=41$	164	49371	17
6	17	10	$64-17=47$	470	48901	18

最终血量 $48901$ ，与样例输出一致；防御随升级上涨，正是「性价比高的先打」能放大的收益。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 18:13
# update_at: 2026-10-02 18:13

import heapq
import sys
from collections.abc import Iterator

INF = float("inf")  # 挨打 0 次的块：一击必杀还白拿升级，性价比视为无穷


def root_tree(g: list[list[int]]) -> list[int]:
    """以 1 为根做迭代 DFS，返回每个点的父亲；1 的父亲记 0。"""
    parent = [0] * len(g)
    parent[1] = -1  # 先占位标记根已访问，遍历完再还原成 0
    stack = [1]
    while stack:
        u = stack.pop()
        for v in g[u]:
            if parent[v] == 0:
                parent[v] = u
                stack.append(v)
    parent[1] = 0
    return parent


def hit_rounds(hp: int, hero_atk: int, monster_def: int) -> int:
    """打死这只怪前英雄要挨的次数：先手打 ceil(hp/(攻-防)) 次，此前挨 t 次反击。"""
    per = hero_atk - monster_def
    return (hp + per - 1) // per - 1


def block_ratio(total_gain: int, total_rounds: int) -> float:
    """块的性价比：每挨一次打能换来多少升级。"""
    return total_gain / total_rounds if total_rounds else INF


def find(f: list[int], x: int) -> int:
    """并查集查块顶，路径压缩。"""
    while f[x] != x:
        f[x] = f[f[x]]
        x = f[x]
    return x


def fight_order(parent: list[int], rounds: list[int], gain: list[int]) -> list[int]:
    """块合并贪心：堆按性价比弹出全局最大的块；块顶的父亲已出战就整块出战
    （块顶先打，子块按弹出先后即性价比降序），否则整块并进父亲所在的块。"""
    n = len(parent) - 1
    f = list(range(n + 1))          # 并查集：指向所在块的块顶
    total_rounds = rounds[:]        # 块累计挨打次数
    total_gain = gain[:]            # 块累计升级
    kids: list[list[int]] = [[] for _ in range(n + 1)]  # 块顶名下已并入的子块
    popped = [False] * (n + 1)      # 块顶弹出过：之后清掉过期堆项
    scheduled = [False] * (n + 1)   # 是否已出战
    scheduled[1] = True             # 1 号点是起点，视为最先出战
    heap = [(-block_ratio(total_gain[i], total_rounds[i]), -i) for i in range(2, n + 1)]
    heapq.heapify(heap)
    order: list[int] = []

    while heap:
        _, neg_u = heapq.heappop(heap)
        u = -neg_u
        if popped[u]:
            continue                # 并块前压入的旧键，块已合并过
        popped[u] = True
        if scheduled[parent[u]]:
            # 父亲已出战：整块立刻出战，块顶最先，子块按并入先后（性价比降序）
            stack = [u]
            while stack:
                x = stack.pop()
                scheduled[x] = True
                order.append(x)
                stack.extend(reversed(kids[x]))
            continue
        # 父亲还没上场：并进父亲的块攒着，合并后的性价比是按挨打次数的加权平均
        p = find(f, parent[u])
        total_gain[p] += total_gain[u]
        total_rounds[p] += total_rounds[u]
        kids[p].append(u)
        f[u] = p
        heapq.heappush(heap, (-block_ratio(total_gain[p], total_rounds[p]), -p))
    return order


def final_hp(order: list[int], hp: int, armor: int, m_atk: list[int],
             rounds: list[int], gain: list[int]) -> int:
    """按出战序列结算血量：每场挨 t×(怪攻-当前防御)；中途阵亡返回 -1。"""
    defense = armor
    for u in order:
        hp -= rounds[u] * (m_atk[u] - defense)
        if hp <= 0:
            return -1
        defense += gain[u]
    return hp


def solve() -> None:
    data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    g: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        x, y = next(data), next(data)
        g[x].append(y)
        g[y].append(x)
    hp, hero_atk, armor = next(data), next(data), next(data)

    # 怪物第 k 行对应节点 k+1：血量、攻击、防御、打完提升的等级
    m_atk = [0] * (n + 1)
    rounds = [0] * (n + 1)
    gain = [0] * (n + 1)
    for u in range(2, n + 1):
        b, a, d, v = next(data), next(data), next(data), next(data)
        m_atk[u], gain[u] = a, v
        rounds[u] = hit_rounds(b, hero_atk, d)

    order = fight_order(root_tree(g), rounds, gain)
    print(final_hp(order, hp, armor, m_atk, rounds, gain))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 22:51
 * update_at: 2026-10-04 22:51
 */

// 牛半仙的魔塔：树上「父亲先于儿子」的块合并贪心。
// 单场战斗的代价是勇士挨打 t = ceil(b/(A-d)) - 1 次，收益是 val 级升级（防御 +val），
// 于是每场战斗的性价比 rho = val / t；父亲必须先打的限制用并查集把「攒着的子块」
// 并进父亲块（新块的 rho 是按挨打次数加权平均），大根堆每次弹出全局 rho 最大的块。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

typedef long long ll;

int n;
vector<int> g[MAXN]; // g[u] 存节点 u 的所有邻居

ll hp, hero_atk, armor; // 勇士初始血量、攻击、盔甲防御
ll monster_atk[MAXN];   // monster_atk[u] 节点 u 魔物的攻击
ll hits[MAXN];          // hits[u] 打死节点 u 的魔物前，勇士要挨的攻击次数
ll gain[MAXN];          // gain[u] 打死节点 u 的魔物后提升的等级（也是防御增量）
int up[MAXN];           // up[u] 节点 u 在树上的父亲，根 1 的父亲为 0

int block_top[MAXN];           // 并查集：指向所在块的块顶
ll block_gain[MAXN];           // 块内累计升级
ll block_hits[MAXN];           // 块内累计挨打次数
vector<int> merged_kids[MAXN]; // merged_kids[x] 已并入块顶 x 的子块，按并入先后排列
int ver[MAXN];                 // 块顶的版本号，用来丢掉堆里的过期键
int scheduled[MAXN];           // 是否已出战（起点 1 视为最先出战）
int order_list[MAXN];          // 最终的出战顺序
int order_cnt;
int work_stack[MAXN]; // 迭代遍历树、展开整块时共用的显式栈

// 堆元素：块的性价比 = block_gain / block_hits，block_hits 为 0 时视为无穷大。
struct BlockNode {
    ll gain_v;
    ll hits_v;
    int id;     // 块顶编号
    int ticket; // 该块顶的版本号，只有等于 ver[id] 的键才有效
};

// priority_queue 默认大根堆，operator< 定义「性价比更小」的一方为更小。
bool operator<(const BlockNode &x, const BlockNode &y) {
    if (x.hits_v == 0 || y.hits_v == 0) {
        if (x.hits_v == 0 && y.hits_v == 0) {
            return x.id < y.id; // 两块都是一击必杀，顺序随意，用编号定序
        }
        return y.hits_v == 0; // x 的性价比有限、y 的无穷大，则 x 更小
    }
    return x.gain_v * y.hits_v < y.gain_v * x.hits_v; // 交叉相乘比较，避免浮点误差
}

priority_queue<BlockNode> heap;

// 并查集查块顶，带路径压缩。
int find_top(int x) {
    while (block_top[x] != x) {
        block_top[x] = block_top[block_top[x]];
        x = block_top[x];
    }
    return x;
}

// 把块顶 u 的当前信息压进堆，并升级它的版本号。
void push_block(int u) {
    ver[u]++;
    BlockNode node;
    node.gain_v = block_gain[u];
    node.hits_v = block_hits[u];
    node.id = u;
    node.ticket = ver[u];
    heap.push(node);
}

void read_input() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> hp >> hero_atk >> armor;

    // 怪物第 k 行对应节点 k + 1，依次是血量 b、攻击 a、防御 d、提升等级 v
    for (int u = 2; u <= n; u++) {
        ll b, a, d, v;
        cin >> b >> a >> d >> v;
        monster_atk[u] = a;
        gain[u] = v;
        // 勇士先手，打死共需 ceil(b/(A-d)) 击，此前只挨 k - 1 次反击
        ll per_hit = hero_atk - d;
        hits[u] = (b + per_hit - 1) / per_hit - 1;
    }
}

// 以 1 为根，用显式栈做迭代 DFS 求出每个点的父亲。
void build_parent() {
    for (int i = 1; i <= n; i++) {
        up[i] = 0;
    }
    int top = 0;
    work_stack[top++] = 1;
    up[1] = -1; // 先占位表示根已访问，遍历完再还原成 0
    while (top > 0) {
        int u = work_stack[--top];
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (up[v] == 0) {
                up[v] = u;
                work_stack[top++] = v;
            }
        }
    }
    up[1] = 0;
}

void solve() {
    for (int i = 1; i <= n; i++) {
        block_top[i] = i;
        block_gain[i] = gain[i];
        block_hits[i] = hits[i];
    }
    scheduled[1] = 1; // 1 号点是起点，没有魔物，视为最先出战
    for (int u = 2; u <= n; u++) {
        push_block(u);
    }

    while (!heap.empty()) {
        BlockNode cur = heap.top();
        heap.pop();
        if (cur.ticket != ver[cur.id]) {
            continue; // 过期键：该块顶后来并过新子块，已压入新版本
        }
        int u = cur.id;
        if (scheduled[up[u]]) {
            // 父亲已出战：整个块立刻出战，块顶最先，子块按并入先后（性价比降序）出战
            int top = 0;
            work_stack[top++] = u;
            while (top > 0) {
                int x = work_stack[--top];
                scheduled[x] = 1;
                order_list[order_cnt++] = x;
                // 逆序压栈，保证先并入的子块先弹出
                for (int i = (int)merged_kids[x].size() - 1; i >= 0; i--) {
                    work_stack[top++] = merged_kids[x][i];
                }
            }
        } else {
            // 父亲还没上场：整块并进父亲所在的块攒着，性价比取按挨打次数的加权平均
            int p = find_top(up[u]);
            block_gain[p] += block_gain[u];
            block_hits[p] += block_hits[u];
            merged_kids[p].push_back(u);
            block_top[u] = p;
            push_block(p);
        }
    }

    // 按出战顺序结算血量；中途死亡输出 -1
    ll cur_hp = hp;
    ll defense = armor;
    for (int i = 0; i < order_cnt; i++) {
        int u = order_list[i];
        cur_hp -= hits[u] * (monster_atk[u] - defense);
        if (cur_hp <= 0) {
            cout << -1 << "\n";
            return;
        }
        defense += gain[u];
    }
    cout << cur_hp << "\n";
}

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

    read_input();
    build_parent();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(n \log n)$ 。每个点至多入堆、出堆各一次，路径压缩的并查集均摊 $O(\alpha(n))$ ，出战序列总长 $n-1$ 。
空间复杂度： $O(n)$ ，存树、并查集、子块链与堆。

总结

这道题的建模核心是把战斗折算成性价比：单场战斗的损失只取决于怪自己的 $t = \lceil b/(A-d) \rceil - 1$ ，全局目标化简为最大化 $\sum_{j \text{ 在 } i \text{ 前}} val_j t_i$ ，于是无约束时按 $\rho = val/t$ 降序即可（相邻交换论证）。

树上「父亲先于儿子」的限制不改变排序思想，只把单个点升级成块：堆弹出 $\rho$ 最大的块，父亲已出战就整块出战，否则并入父亲的块（加权平均），并查集维护块顶。弹出值单调不增保证了块内子块顺序正是 $\rho$ 降序，块交换引理保证了整块方案不劣于任意交错方案。

实现上注意：怪物第 $k$ 行对应节点 $k+1$ ；英雄先手使挨打次数是 $t = \text{ceil} - 1$ 而非 $\text{ceil}$ ；出战序列用显式栈展开，避免 $O(n)$ 深的递归。本地用 10 组真实评测数据验证，输出全部一致，与正解同为 $O(n \log n)$ 。

目录

形式化题目

正解

思路

代码

复杂度

总结