题意:
一棵结点数为n的树,除1号结点外都有一个怪兽,消灭第i个结点上的怪兽会消耗ai的HP,但消灭完之后会恢复bi的HP。现在从结点1出发去打怪,最少初始时含有多少HP才能保证能打完所有的怪,而且任何时候的HP都不为负。

题解:
以1为根,将无根树变为有根树。要想消灭结点x的怪兽,必须先消灭x的父亲结点上的怪兽。

当不考虑消灭要先消灭的父亲的限制时,就是说可以随便、任意选择顺序的情况。

考虑两个结点i和j的消灭顺序:

若两者都是啊a<b的情况,说明消灭后会提升HP,所以应该优先消灭(相对于会降低HP的结点),但不同的顺序对于初始的HP的要求不同,所以应该优先消灭需要“本钱”少的,就是要以a的升序来消灭怪兽。

若两者都是a>b的情况,考虑最后最后一定是可以消灭完所有的怪兽的(因为初始可以有足够的HP),那么消灭完最后一个怪兽后,所剩的HP一定最后一个怪兽的b,这是显然的,不然会有“浪费”。由于初始HP和最后HP的差值与顺序无关(都是),所以要使初始HP最小,最后所剩的HP也应该最小。就是要以b的降序来消灭怪兽。

若两者一个满足a<b,一个满足a>b,肯是要先消灭能提升HP的那一个。

根据以上关系就可以确定怪兽消灭的优先级。

现在考虑加上消灭x,必须先消灭father[x]的限制:

考虑先在优先级最高的结点:x,必须先消灭father[x],而且是消灭完father[x]后,就应该立刻取消灭x,因为x在那里已经等着被消灭的望穿秋水了。于是我们就可以将father[x]和x两个结点当作一个结点考虑,将两个结点“合并”成一个结点,然后合并n-2次就合并成一个结点了,这时的a就是答案。

合并方法:

father[x]的b值大于x的b值,那么father[x]新的b值为b-bx

father[x]的b值小于x的b值,那么father[x]新的a值为a+(ax-b),b值为bx。

代码:

#include<bits/stdc++.h>
#define N 100010
#define INF 1e9
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define eps 1e-8
#define P 1000000007
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
struct node
{
	LL x,y,id;
	bool operator <(const node z) const
	{
	    if (x<y && z.x<z.y) return x>z.x;
		if (y<=x && z.y<=z.x) return y<z.y;
		if (y<=x && z.y>z.x) return true;
		return false;
	}
}a[N];
priority_queue<node>q;
int fa[N];
bool v[N];
vector<int>G[N];

void dfs(int x,int p)
{
	for(auto i:G[x])if (i!=p) fa[i]=x,dfs(i,x);
}

int getfa(int x)
{
	if (!v[fa[x]]) return fa[x];
	return fa[x]=getfa(fa[x]);
}

int main()
{
	IO
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for (int i=2;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y;a[i].id=i;
			q.push(a[i]); v[i]=0; G[i].cl();
		}
		G[1].cl(); a[1].x=a[1].y=a[1].id=0; fa[1]=1; v[1]=0;
		for (int i=1;i<n;i++)
		{
			int j,k;
			cin>>j>>k;
			G[j].pb(k);G[k].pb(j);
		}
		dfs(1,0);
		while(!q.empty())
		{
			node c=q.top();q.pop();
			if (!(c.x==a[c.id].x && c.y==a[c.id].y) || v[c.id]) continue;
			int ff=getfa(c.id); node t=a[ff];
			a[ff].x+=max(a[ff].y,a[c.id].x)-a[ff].y;
			if (a[ff].y>a[c.id].x)a[ff].y-=(a[c.id].x-a[c.id].y);else a[ff].y=a[c.id].y;
			if (ff!=1 && !(a[ff].x==t.x && a[ff].y==t.y)) q.push(a[ff]);
			v[c.id]=1;
		}
		cout<<a[1].x<<endl;
	}
	return 0;
}