题目链接：https://ac.nowcoder.com/acm/problem/212915

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109320382

题目

牛半仙的妹子被大魔王抓走了，牛半仙为了就他的妹子，前往攻打魔塔。
魔塔为一棵树，牛半仙初始在一号点。
牛半仙有攻击，防御，血量三个属性。
除一号点外每个点都有魔物防守，魔物也有攻击，防御，血量三个属性。
每个怪物后面都守着一些蓝宝石，获得 蓝宝石可增加 防。
牛半仙具有突袭属性，所以遇到魔物后会率先发动攻击，然后牛半仙和魔物轮换地攻击对方。
一个角色被攻击一次减少的血量是对方的攻击减去自己的防御。
当一个角色的血量小于等于 时，他就会死亡。
当牛半仙第一次到达某个节点时会与这个节点的魔物发生战斗。
当一个魔物死亡后，这个魔物所在的节点就不会再产生新的魔物。
现在牛半仙想知道他打死魔塔的所有魔物后的最大血量。

输入

第一行一个 代表节点数。
随后 行，每行两个数 ，表示 与 节点有边相连。
随后一行，三个数，依次为勇士的血量、攻击、防御。
随后 行，每行四个数，依次为怪物的血量、攻击、防御，和其守着的蓝宝石数量。

输出

一个数，代表最大血量。如果牛半仙在打死魔塔的所有魔物之前就已经死亡了，则输出 。

样例输入

6
1 2
1 3
1 4
4 5
5 6
50000 10 0
35 54 2 4
25 55 3 5
21 51 4 5
20 64 5 3
43 64 6 1

样例输出

48901

样例解释

打怪的顺序依次为 4，3，5，2，6
可以证明不存在更优的方案。

数据范围

对于 的数据：
又有 的数据：，且保证对于每一条边 ，一定满足
对于前 的数据：，且保证对于每一条边 ，一定满足 或
对于最后 的数据：，且保证对于每一条边 ，一定满足 或
对于 的数据：有牛半仙血量 ，攻击 ，盔甲防御 。怪物血量为 ，攻击 ，防御 ，打完一只怪后获得的蓝宝石数量为 至

思路

这道题是一道贪心。

首先我们观察数据，可得牛半仙是不会被打死，怪物的攻击不会被完全防御，牛半仙一定可以打死怪物等信息。

我们可以直接通过公式算出在没有蓝宝石的时候，打怪物要扣多少血。然后拿到宝石之后，再补回血量。
但是我们怎么确定打怪物的顺序呢？

其实我们可以让第一个打你的怪物的蓝宝石数除以打你的次数（我们叫它性价比）尽可能的小。
为什么呢？
我们要让这个蓝宝石在以后发挥更大的作用，就是要让打你次数多的放在后面。

那我们就维护一个大根堆（以性价比为关键字），每一次取出最大的那一个，然后就把能走到的没走过的点放进堆。而且加上能补回的血量。（就是加上一直以来获得的蓝宝石但不算这一次的，乘这个怪物打的次数）

然后最后输出剩下的血量就可以了。

比赛时

代码

#include<queue>
#include<cstdio>
#define ll long long

using namespace std;

struct node {
    int to, nxt;
}e[200001];
priority_queue <pair<double, int> > a;//以性价比为关键字的大根堆
int n, x, y, le[100001], KK, fa[100001], fath[100001], X;
ll blood[100001], at[100001], hold[100001], blue[100001], time[100001];
bool in[100001];

void add(int x, int y) {
    e[++KK] = (node){y, le[x]}; le[x] = KK;
    e[++KK] = (node){x, le[y]}; le[y] = KK;
}

void dfs(int now, int father) {
    for (int i = le[now]; i; i = e[i].nxt)
        if (e[i].to != father) {
            fa[e[i].to] = now;
            dfs(e[i].to, now);
        }
}

int find(int now) {
    if (now == fath[now]) return now;
    return fath[now] = find(fath[now]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &x, &y);
        add(x, y);
    }

    fath[1] = 1;
    scanf("%lld %lld %lld", &blood[1], &at[1], &hold[1]);
    for (int i = 2; i <= n; i++) {
        fath[i] = i;
        scanf("%lld %lld %lld %lld", &blood[i], &at[i], &hold[i], &blue[i]);
        time[i] = blood[i] / (at[1] - hold[i]);
        if (blood[i] % (at[1] - hold[i]) == 0) time[i]--;//算出要打多少次
        blood[1] -= (at[i] - hold[1]) * time[i];//假设没有蓝宝石，扣血
        a.push(make_pair(1.0 * blue[i] / time[i], i));
    }

    dfs(1, 0);

    in[1] = 1;
    while (!a.empty()) {
        int now = a.top().second;
        a.pop();
        if (in[now]) continue;
        in[now] = 1;
        X = find(fa[now]);
        blood[1] += time[now] * blue[X];//补回蓝宝石保留的血量
        time[X] += time[now];
        blue[X] += blue[now];
        if (!in[X]) a.push(make_pair(1.0 * blue[X] / time[X], X));
        fath[now] = X;//并查集
    }

    printf("%lld", blood[1]);

    return 0;
}