【GOJ 1489】Monster Hunter

题目

正解

首先，这是一棵有根树，其次，很明显每只怪物都要父亲怪物被击杀后才可以被击杀，我们不妨想问题的时候从简单的出发，就是：假如没有父亲这个限制，我们应该怎样打怪物呢，首先我们可以把怪物分成两类: (a lt b)和 (a geq b)的，前面一类打完不会掉血，后面则会掉血，那么这时候肯定先把前面一类的打完之后再打第二类的是更加优的。

• (a lt b)的怪物呢，我们也应该按照a从小到大的顺序打。

• (a geq b)的怪物呢，考虑两只怪物的击杀顺序(i，j)，那么有两种情况:先打(i)或者先打(j)。

• (i)有(HP+min(-a[i]，-a[i]+b[i]-a[j]))， 因为(age b) ，所以有(HP-a[i]-a[j]+b[i])。

  • 先打(j)同理有(HP-a[i]-a[j]+b[j])，可以发现 (HP-a[i]-a[j])是一样需要的，所以我们应该按照b的从大到小的顺序打。

那么我们这样就可以在(O(1))的时间内比较出应该先打谁了，假设忽略了父亲限制之后的攻击顺序为(p_1，p_2，..，p_n)。

• (p_1=1)，那么第一步打(p_1)一定是最优的。

• (p_1!=1)，那么在打完(p_1)的父亲(x)后，紧接着打(p_1)一定是最优的，直接把(p_1)和(x)的两只怪物合并，依然用((a，b))表示，并且把(p_1)所有儿子的父亲改为(x)就可以消除(p_1)的影响了，么每次消除(1)个，算法复杂度为(o(n))。

很明显需要支持修改一个怪物，删除最优怪物，以为修改父亲的操作;那么找最优怪物，我们可以用优先队列，对于修改父亲，我们可以用并查集维护就ok，所以总的复杂度应该是(o(nlogn))。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
typedef long long ll;
char cch;
inline int rd(){
	int x=0,fl=1;
	cch=getchar();
	while(cch>'9'||cch<'0'){
		if(cch=='-') fl=-1;
		cch=getchar();
	}
	while(cch>='0'&&cch<='9') x=(x<<3)+(x<<1)+cch-'0',cch=getchar();
	return x*fl;
}
const int N=1e5+3;
struct abc{
	int i;
	ll a,b;
	bool operator <(const abc & x)const{
		int sn1=a<b,sn2=x.a<x.b;
		if(sn1<sn2) return true;
		if(sn1==sn2){
			if(a<b) return a>x.a;
			return b<x.b;
		}
		return 0;
	}
}a[N];
bool vis[N];
int to[N<<1],cnt,nxt[N<<1],fa[N],head[N];
inline void adde(int u,int v){
	to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
	to[++cnt]=u,nxt[cnt]=head[v],head[v]=cnt;
}
inline void dfs(int x,int f){
	fa[x]=f;
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=f){
		dfs(to[i],x);
	}
}
inline int getfa(int x){
	if(!fa[x]||!vis[x]) return x;
	return fa[x]=getfa(fa[x]);
}
priority_queue<abc> q;
int main(){//问题相当于求：Hp初始为0，可以随时购买，最少需要买多少Hp 
	int n=rd(),u,v;
	abc t;
	rep(i,2,n) a[i].a=rd(),a[i].b=rd(),a[i].i=i,q.push(a[i]);
	rep(i,2,n) u=rd(),v=rd(),adde(u,v);
	dfs(1,0);
	ll tmp;
	while(!q.empty()){
		t=q.top();q.pop();
		u=t.i;
		if(vis[u]||((t.a!=a[u].a)||(t.b!=a[u].b))) continue;
		vis[u]=1;
		v=getfa(u);
		tmp=max(a[v].a,a[u].a+a[v].a-a[v].b);//购买需要的 Hp 
		a[v].b=a[u].b+a[v].b-a[u].a-a[v].a+tmp;//总受益，加上tmp是因为 你为了Hp始终>=0购买了tmp的Hp，所以相当于凭空获得tmp 
		a[v].a=tmp;
		/*if(v>1)*/ q.push(a[v]);
	}
	printf("%lld",a[1].a); 
}

来源