正解
首先，这是一棵有根树，其次，很明显每只怪物都要父亲怪物被击杀后才可以被击杀，我们不妨想问题的时候从简单的出发，就是：假如没有父亲这个限制，我们应该怎样打怪物呢，首先我们可以把怪物分成两类: \(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])\)， 因为\(a\ge 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);
}