2020牛客NOIP賽前集訓營-提高組（第三場）T4牛半仙的魔塔（增強版）

題目描述

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

魔塔為一棵樹，牛半仙初始在一號點，

牛半仙有攻擊，防御，血量三個屬性，

除一號點外每個點都有魔物防守，魔物也有攻擊，防御，血量三個屬性，

每個怪物后面都守著一些藍寶石，獲得1藍寶石可增加1防，

牛半仙具有突襲屬性，所以遇到魔物后會率先發動攻擊，然后牛半仙和魔物輪換地攻擊對方，

一個角色被攻擊一次減少的血量是對方的攻擊減去自己的防御，

當一個角色的血量小于等于 0 時，他就會死亡，

當牛半仙第一次到達某個節點時會與這個節點的魔物發生戰斗，

當一個魔物死亡后，這個魔物所在的節點就不會再產生新的魔物，

現在牛半仙想知道他打死魔塔的所有魔物后的最大血量，

輸入描述:

第一行一個 n 代表節點數， 隨后 n-1 行，每行兩個數 i,j，表示 i 與 j 節點有邊相連，
隨后一行，三個數，依次為勇士的血量、攻擊、防御， 隨后 n-1 行，每行四個數，依次為怪物的血量、攻擊、防御，和其守著的藍寶石數量，

輸出描述:

一個數，代表最大血量，如果牛半仙在打死魔塔的所有魔物之前就已經死亡了，則輸出 -1，

備注:

對于100%的資料: n ≤ 1 0 5 n \le 10^5 n≤105，樹
對于100%的資料：有牛半仙血量 < 5 ? 1 0 18 <5*10^{18} <5?1018，攻擊 = 2000 =2000 =2000，盔甲防御 = 0 =0 =0，怪物血量為 3000 3000 3000 ~
1 0 6 10^6 106，攻擊 5 × 1 0 5 5×10^5 5×105? 7 × 1 0 5 7\times 10^5 7×105，防御 ≤ 1000 \leq 1000 ≤1000，打完一只怪后獲得的藍寶石數量為 1 1 1至 5 5 5

官方題解看懂 自己琢磨了一下想通了
所以寫個通俗 ju ruo 點兒的

考慮第 i i i個攻擊的怪

記第 i i i個怪有 b i b_i bi?個藍寶石

因為怪的血量和攻擊和防御是不變的 勇士的攻擊也是不變的

所以它會被勇士攻擊 ? 血 量 勇 士 攻 擊 ? 防 御 ? \lceil\dfrac{血量}{勇士攻擊-防御}\rceil ?勇士攻擊?防御血量?? 輪

并攻擊勇士 ? 血 量 勇 士 攻 擊 ? 防 御 ? ? 1 \lceil\dfrac{血量}{勇士攻擊-防御}\rceil -1 ?勇士攻擊?防御血量???1 輪 可直接求出 記為 h i h_i hi?

造成的傷害為 h i × ( 攻 擊 ? 初 始 防 御 ? ∑ j = 1 i ? 1 b i ) h_i\times (攻擊-初始防御-\sum_{j=1}^{i-1}b_i) hi?×(攻擊?初始防御?∑j=1i?1?bi?)

總傷害為 ∑ i = 1 n h i × ( 攻 擊 ? 初 始 防 御 ? ∑ j = 1 i ? 1 b i ) \sum_{i=1}^n h_i\times (攻擊-初始防御-\sum_{j=1}^{i-1}b_i) ∑i=1n?hi?×(攻擊?初始防御?∑j=1i?1?bi?)

求這個的最小值 即求 ∑ i = 1 n h i × ∑ j = 1 i ? 1 b i \sum_{i=1}^n h_i\times \sum_{j=1}^{i-1}b_i ∑i=1n?hi?×∑j=1i?1?bi? 的最大值

可以推出按照權值 t i = h i b i t_i=\dfrac{h_i}{b_i} ti?=bi?hi?? 升序排出來的答案最優

證明：若最優的情況為： h 1 , h 2 . . . h n h_1,h_2...h_n h1?,h2?...hn? ， 交換 i i i, i + 1 i+1 i+1答案的改變數是 h i × b i + 1 ? h i + 1 × b i < 0 h_i\times b_{i+1}-h_{i+1}\times b_i<0 hi?×bi+1??hi+1?×bi?<0

即 h i b i < h i + 1 b i + 1 \dfrac{h_i}{b_i}<\dfrac{h_{i+1}}{b_{i+1}} bi?hi??<bi+1?hi+1?? 得證 （感性理解也可）

考慮貪心 我們先攻擊 t i t_i ti? 小的 再攻擊大的

顯然不行 比如一個 t i t_i ti?大的點有很多 $ t_i$ 小的子節點

這里給出一個結論
若兒子節點 y y y 的 t t t 小于父親節點 x x x 的 t t t
那么攻擊了的父親節點 x x x 過后 會立即攻擊兒子 y y y （這里好好想想為什么）

根據這個結論 我們可以從權值最小的節點開始 若節點 y y y 的權值小于父親 x x x
這就意味著會連續攻擊 x , y x,y x,y
我們就把 y y y 合并到 x x x 上 合并成一個大點

這個大點的權值 t t t 變成 ∑ h i ∑ b i \dfrac{\sum h_i}{\sum b_i} ∑bi?∑hi??

證明：若 1 1 1號節點和 2 2 2節點要連續攻擊 比較下面兩種情況對答案的貢獻

① 按 1 , 2 , 3 1,2,3 1,2,3 排 h 2 × b 1 + h 3 × ( b 1 + b 2 ) h_2\times b_1+h_3\times (b_1+b_2) h2?×b1?+h3?×(b1?+b2?)

② 按 3 , 1 , 2 3,1,2 3,1,2 排 h 1 × b 3 + h 2 × ( b 3 + b 1 ) h_1\times b_3+h_2\times (b_3+b_1) h1?×b3?+h2?×(b3?+b1?)

①-②得 h 3 ( b 1 + b 2 ) ? ( h 1 + h 2 ) b 3 h_3(b_1+b_2)-(h_1+h_2)b_3 h3?(b1?+b2?)?(h1?+h2?)b3?

比較答案大小即比較的是 h 1 + h 2 b 1 + b 2 \dfrac{h_1+h_2}{b_1+b_2} b1?+b2?h1?+h2??和 h 3 b 3 \dfrac{h_3}{b_3} b3?h3?? 的大小 所以大點的權值為 ∑ h i ∑ b i \dfrac{\sum h_i}{\sum b_i} ∑bi?∑hi?? 得證

從權值最小的節點開始 若點 y y y 的權值小于父親所在的大點 x x x 就把 y y y 合并到 x x x 上 合并成一個大點

處理完后就從根節點開始 貪心地選擇可以到達點中 權值最小的點

所形成的順序就是攻擊怪物的順序了

#include <bits/stdc++.h>
#define N 210000
using namespace std;
typedef long long ll;
int n;
int f[N],nxt[N],data[N],num,fa[N],ff[N];
ll ans;
bool tag[N];
struct node{
	ll val,siz,pos;
}h[N];
inline bool operator <(node x,node y){ return 1ll*x.val*y.siz>1ll*y.val*x.siz; }
inline void add(int x,int y){ nxt[++num]=f[x]; f[x]=num; data[num]=y; }
priority_queue<node> q;
inline int findf(int x){ return fa[x]==x?x:fa[x]=findf(fa[x]); }
inline void dfs(int x){
	int y;
	for(int i=f[x];i;i=nxt[i]){
		y=data[i]; if(y==ff[x])continue;
		ff[y]=x; dfs(y); 
	}
}
int main(){
	cin>>n;
	ll x,y,z,a,b;
	for(int i=1;i<n;i++){ scanf("%lld %lld",&x,&y); add(x,y); add(y,x); }
	scanf("%lld %lld %lld",&ans,&a,&b); fa[1]=1;
	h[1].siz=b;
	for(int i=2;i<=n;i++){
		fa[i]=i;
		scanf("%lld %lld %lld %lld",&z,&x,&y,&h[i].siz);
		h[i].val=z/(a-y); if(z%(a-y)!=0)h[i].val++;
		h[i].val--;
		ans-=(x-b)*h[i].val;
		h[i].pos=i;
		q.push(h[i]);
	}
	dfs(1);
	node u;
	while(!q.empty()){
		u=q.top(); q.pop(); x=u.pos;
		if(tag[x])continue; tag[x]=1;
		y=findf(ff[x]);
		ans+=h[y].siz*h[x].val;
		h[y].val+=h[x].val; h[y].siz+=h[x].siz;
		if(y!=1&&tag[y]==0)q.push(h[y]);
		fa[x]=y;
	}
	cout<<ans;
}

講得不清楚就問哦 畢竟蒟蒻描述能力真的…不太好