[牛客2020提高赛前集训营day3] 牛半仙的魔塔

题目描述

牛半仙的妹子被大魔王抓走了，牛半仙为了就他的妹子，前往攻打魔塔。

魔塔为一棵树，牛半仙初始在一号点。
牛半仙有攻击，防御，血量三个属性。
除一号点外每个点都有魔物防守，魔物也有攻击，防御，血量三个属性。
每个怪物后面都守着一些蓝宝石，获得 $1$ 蓝宝石可增加 $1$ 防。

牛半仙具有突袭属性，所以遇到魔物后会率先发动攻击，然后牛半仙和魔物轮换地攻击对方。
一个角色被攻击一次减少的血量是对方的攻击减去自己的防御。
当一个角色的血量小于等于 $0$ 时，他就会死亡。

当牛半仙第一次到达某个节点时会与这个节点的魔物发生战斗。
当一个魔物死亡后，这个魔物所在的节点就不会再产生新的魔物。
现在牛半仙想知道他打死魔塔的所有魔物后的最大血量。

输入格式

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

输出格式

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

样例

样例输入1：

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

样例输出1：

48901

样例解释：
打怪的顺序为 $4,3,5,2,6$。

可以证明不存在更优的方案。

数据范围

对于 $10\%$ 的数据，$n\le 15$。
另有 $10\%$ 的数据，$n\le 10^5$，只存在边 $(1,i)$。
另有 $10\%$ 的数据，$n\le 10^5$，只存在边 $(1,i),(i-1,i)$。
另有 $30\%$ 的数据，$n\le 10^3$。
对于 $100\%$ 的数据，$n\le 10^5$，牛半仙的血量 $\le 5\times 10^{18}$，攻击 $=2000$，盔甲防御 $=0$，怪物血量为 $3000\sim 10^6$，攻击 $5\times 10^5-7\times 10^5$，防御 $\le 1000$，打完一只怪后获得的蓝宝石数量为 $1$ 至 $5$。

题解

这道题的思路还是很妙的，不一定能想到。

思路：

观察到数据范围 $n\le 10^5$，看起来并不是 dp，考虑贪心。

假设牛半仙的攻击，防御，血量分别为 $rx,ry,rz$，每个结点的怪物的攻击，防御，血量，宝石数为 $p_i,q_i,r_i,s_i$，考虑两个怪物应该如何攻击顺序更优。

我们用 $p_1,q_1,r_1,s_1$ 代表第一个怪物，$p_2,q_2,r_2,s_2$ 代表第二个怪物。

先攻击第一个怪物的血量损失：$(\lceil r_1/(rx-q_1)\rceil -1)\times \max (p_1-ry,0)+(\lceil r_2/(rx-q_2)\rceil -1)\times \max (p_2-ry-s_1,0)$。

先攻击第二个怪物的血量损失：$(\lceil r_2/(rx-q_2)\rceil -1)\times \max (p_2-ry,0)+(\lceil r_1/(rx-q_1)\rceil -1)\times \max (p_1-ry-s_2,0)$。

比较条件：$(\lceil r_1/(rx-q_1)\rceil -1)\times \max (p_1-ry,0)+(\lceil r_2/(rx-q_2)\rceil -1)\times \max (p_2-ry-s_1,0)<(\lceil r_2/(rx-q_2)\rceil -1)\times \max (p_2-ry,0)+(\lceil r_1/(rx-q_1)\rceil -1)\times \max (p_1-ry-s_2,0)$。

由于牛半仙的攻击不变，怪物的血量和防御不变，因此攻击次数不变，我们分别把它设为 $t1,t2$。

原式写为：$t_1\times \max (p_1-ry,0)+t_2\times \max (p_2-ry-s_1,0)<t_2\times \max (p_2-ry,0)+t_1\times \max (p_1-ry-s_2,0)$。

我们发现，如果 $p_1\ge ry+s_2$ 且 $p_2\ge ry+s_1$，则原式可以化简为 $t_1\times s_2<t_2\times s_1$。

如果去掉 $\max$，也没有什么影响。如果计算出来的式子 $<0$，化简后影响到的是减去了 $s_1$ 或 $s_2$ 的那个 $t_1$ 或 $t_2$，防御已经大于攻击了，将它排在前面一定更优，这个式子也能解决这个问题。

考虑一下如果左右两边相等的情况，实际上交换两个怪物的顺序并不影响到损失的血量，可以用上面的式子解决。

由于我们在 $1$ 号结点，攻击一个子结点一定要攻击它的父亲结点，那么如果一定要选择子结点，那么选完父亲结点一定就会选子结点，那就会考虑到每棵子树的 $t_i/s_i$ 的值。实际上，$t_i$ 和 $s_i$ 是可以进行合并的。

假如我们有三个结点 $h_1,h_2,h_3$，$1,2$ 结点要连续攻击，顺序为 $1,2,3$ 时是 $s_1\times t_2+(s_1+s_2)\times t_3$，顺序为 $3,1,2$ 时是 $s_3\times t_1+(s_3+s_1)\times t_2$，比较条件为 $s_1\times t_2+(s_1+s_2)\times t_3<s_3\times t_1+(s_3+s_1)\times t_2$，化简为 $(s_1+s_2)\times t_3<s_3\times (t_1+t_2)$，也就是可以直接合并。

接下来我们将所有结点扔进堆中，每次贪心的选出 $t/s$ 最小的结点，用并查集将它合并到父亲结点，如果它的父亲已经选过了，那么就可以计算这个子树选的点的最小血量损失值，然后把这些选的结点标记为已选。

然后最后输出剩下的血量就可以了，时间复杂度 $n\log n$，瓶颈在堆上。

实现

由于我们合并时会破坏原来的 $t$ 和 $s$，因此我们开另外一个数组 $b$ 记录 $t_i,s_i,b{h}_i$（$bh$ 即结点编号）。堆的比较条件为 $t_1\times s_2<t_2\times s_1$，但是如果两边相等，那么系统比较时都返回 $0$，系统会认为这两个元素相等，进而导致与其他元素比较时的错误，而且可能导致堆的时间复杂度退化为 $n^2$，因此如果相等，我们可以按 $bh$ 排序，这样就不会出现问题。或者你也可以开一个 pair<double, int> 的堆，第一个表示 $t/s$ 的值，第二个表示 $bh$，也可以避免这个问题，不过会有精度误差。

在取出一个结点 $t$ 后，如果它的父亲没选，就将它的父亲结点的所属并查集的根 $o$ 找出来（$getfather$），然后把 $t$ 的两个属性 $t,s$ 加到 $o$ 上，将 $t$ 的所属并查集设到 $o$，记录路径 $o\to t$，最后把 $o$ 扔进堆。如果它的父亲选了，递归计算，按记录路径顺序计算。

然后注意开 long long（我因为省事直接全部开了）。

#include<bits/stdc++.h>
using namespace std;
long long n, rx, ry, rz;
vector<long long> v[100010];
struct node{long long p, q, r, s, t, bh;//攻击，防御，血量，宝石，攻击次数，编号
}a[100010];
struct node2{long long s, t, bh;friend bool operator<(node2 a, node2 b){long long t1 = a.s * b.t, t2 = b.s * a.t;if(t1 == t2) return a.bh < b.bh;return t1 < t2; }
}b[100010];
priority_queue<node2> pq;
long long vis[100010], fl[100010];
long long ft[100010], u[100010];
vector<long long> vc[100010];
void dfs(long long x, long long fa){//求每个结点的fatherft[x] = fa;for(auto i : v[x]){if(i == fa) continue;dfs(i, x);}
}
void dfs2(long long x){//计算血量rz -= a[x].t * max(a[x].p - ry, 0ll);ry += a[x].s;fl[x] = 1;for(auto i : vc[x]){dfs2(i);}
}
long long get_father(long long x){if(u[x] == x) return x;return u[x] = get_father(u[x]);
}
int main(){scanf("%lld", &n);for(long long i = 1; i < n; ++ i){long long x, y;scanf("%lld %lld", &x, &y);v[x].push_back(y);v[y].push_back(x);}scanf("%lld %lld %lld", &rz, &rx, &ry);for(long long i = 2; i <= n; ++ i){scanf("%lld %lld %lld %lld", &a[i].r, &a[i].p, &a[i].q, &a[i].s);if(rx <= a[i].q){printf("-1");return 0;}a[i].t = (a[i].r - 1) / (rx - a[i].q);a[i].bh = i;b[i].t = a[i].t;b[i].bh = i;b[i].s = a[i].s;}dfs(1, 0);for(long long i = 2; i <= n; ++ i){pq.push(b[i]);}for(long long i = 1; i <= n; ++ i){u[i] = i;}fl[1] = 1;while(!pq.empty()){node2 t = pq.top();pq.pop();if(vis[t.bh]) continue;vis[t.bh] = 1;if(fl[ft[t.bh]]){//父亲结点选过dfs2(t.bh);continue;}//合并long long t1 = get_father(ft[t.bh]);b[t1].s += b[t.bh].s;b[t1].t += b[t.bh].t;u[t.bh] = t1;vc[t1].push_back(t.bh);pq.push(b[t1]);}if(rz <= 0){printf("-1\n");return 0;}printf("%lld", rz);return 0;
}