先考虑没有树的限制，即我们可以任意安排顺序打怪兽，那么这就是一个全序问题。
考虑在某种顺序下，假设初始血量为 \(st\)，那么打到第 \(i\) 个怪物时剩余的血量就是 \(st+\sum\limits_{j=1}^{i-1}(b_j-a_j)\)，如果设 \(sum_i=\sum\limits_{j=1}^{i-1}(b_j-a_j)\)，那么我们就需要保证 \(\forall i,st+sum_i\geq a_i\)，于是在这种顺序下 \(st\) 的最小值为 \(\max\limits_{i=1}^n(a_i-sum_i)\)。我们要使 \(st\) 最小。
考虑在当前的某种顺序下，交换 \(i\) 和 \(i+1\) 什么时候不优。由于交换 \(i\) 和 \(i+1\) 不会对 \(i+1\) 后面造成影响，所以我们只需要考虑让 \(\max\limits_{j=1}^{i+1}(a_j-sum_j)\) 最小即可。设 \(pre=\max\limits_{j=1}^{i-1}(a_j-sum_j)\)，\(s=sum_i\)。
交换前：\(ans_1=\max(pre,a_i-s,a_{i+1}-(s+(b_i-a_i)))=\max(pre,a_i-s,a_{i+1}-s+a_i-b_i)\)。
交换后：\(ans_2=\max(pre,a_{i+1}-s,a_i-(s+(b_{i+1}-a_{i+1})))=\max(pre,a_{i+1}-s,a_{i}-s+a_{i+1}-b_{i+1})\)。
我们要求的是什么时候 \(ans_1\leq ans_2\)。
直接讨论好像有点难处理，如果我们知道 \(a_i-b_i\) 和 \(a_{i+1}-b_{i+1}\) 的正负性就好了。
这里有一个贪心。我们将怪兽分成两类：\(b_i>a_i\) 的和 \(b_i\leq a_i\) 的，前一类打完会加血，后一类打完会扣血。
我们肯定先打加血再打扣血的，因为先打扣血的没有任何好处。所以 \(b_i>a_i\) 一定放在前面，\(b_i\leq a_i\) 的一定放在后面。
所以我们可以对这两类分类讨论：
- 第一类：若 \(b_i>a_i\) 且 \(b_{i+1}>a_{i+1}\)。那么由上面的式子可知 \(ans_1\leq ans_2\) 的一个充分条件为 \(a_i\leq a_{i+1}\)。于是得到结论这一类中先打 \(a_i\) 小的一定更优，因为如果你先打了某个 \(a_i\) 大的再打某个 \(a_i\) 小的，那么交换这两个的打的顺序一定会更优。
- 第二类：若 \(b_i\leq a_i\) 且 \(b_{i+1}\leq a_{i+1}\)。那么由上面的式子可知 \(ans_1\leq ans_2\) 的一个充分条件为 \(b_i\geq b_{i+1}\)。于是得到结论这一类中先打 \(b_i\) 大的一定更优，因为如果你先打了某个 \(b_i\) 小的再打某个 \(b_i\) 大的，那么交换这两个的打的顺序一定会更优。
所以我们得到结论：先打 \(b_i>a_i\) 的一定比先打 \(b_i\leq a_i\) 的更优，\(b_i>a_i\) 的中先打 \(a_i\) 小的一定更优，\(b_i\leq a_i\) 中先打 \(b_i\) 大的一定更优。这样每一个怪兽都有了一个优先级。
那么如果加入了树的限制会怎么样呢？和 AGC023F 一样，直接用并查集+可删堆维护即可。
代码如下：（常数有点大，2995ms卡过去的）
#include<bits/stdc++.h>
#define N 100010
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int rt[N];
int t,n,fa[N];
int cnt,head[N],nxt[N<<1],to[N<<1];
bool del[N];
ll a[N],b[N];
inline void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u)
{
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa[u]) continue;
fa[v]=u;
dfs(v);
}
}
struct cmp
{
inline bool operator()(const int &x,const int &y) const
{
if((b[x]>a[x])^(b[y]>a[y])) return b[x]>a[x];
if(b[x]>a[x])
{
if(a[x]!=a[y]) return a[x]<a[y];
return x<y;
}
else
{
if(b[x]!=b[y]) return b[x]>b[y];
return x<y;
}
}
};
set<int,cmp>s;
inline int find(int x)
{
return x==rt[x]?x:(rt[x]=find(rt[x]));
}
int main()
{
t=read();
while(t--)
{
n=read();
cnt=0;
for(int i=1;i<=n;i++)
head[i]=0,del[i]=0,rt[i]=i;
for(int i=2;i<=n;i++)
a[i]=read(),b[i]=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
adde(u,v),adde(v,u);
}
dfs(1);
del[1]=1;
for(int i=2;i<=n;i++) s.insert(i);
ll sum=0,ans=0;
while(!s.empty())
{
const int u=(*s.begin());
s.erase(s.begin());
const int f=find(fa[u]);
if(del[f])
{
del[u]=1;
ans=max(ans,a[u]-sum);
sum+=b[u]-a[u];
continue;
}
s.erase(f);
rt[u]=f;
ll na,nb;
if(a[f]>a[f]-b[f]+a[u]) na=a[f],nb=b[f]+b[u]-a[u];
else na=a[f]-b[f]+a[u],nb=b[u];
a[f]=na,b[f]=nb;
s.insert(f);
}
printf("%lld\n",ans);
}
return 0;
}
原文地址：http://www.cnblogs.com/ez-lcw/p/16837422.html
