题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6326
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
const int maxn =1e5+5;
const int mod=9999991;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：树形结构，每个点有个伤害值和增益值，
先扣伤害值再补增益值，主角的血量不能小于0，
主角从根节点出发，问要遍历完所有点，最少需要多少起始血量。贪心，首先按特定的顺序给树上的节点排序，
先把点分为两类，一类是最终有增益的点，一类是最终扣伤害的点，
在增益点里面，按伤害值从小到大排序，
在扣伤害的点中，按增益值从大到小排序，
丢到优先队列里面，先用父节点数组把整棵树的关系构造出来，
然后通过并查集来构造已经合并的节点，
详细方法见代码。时间复杂度：O（nlogn），
wa了三次，看题解最终调整了下排序细节。
*////链式前向星
struct node
{int u,nxt;
}e[maxn<<1];
int head[maxn],tot=0;
void init()
{memset(head,-1,sizeof(head));tot=0;
}
void add(int x,int y)
{e[tot]=node{y,head[x]};head[x]=tot++;
}ll A[maxn],B[maxn],n;
int a,b;int fa[maxn],pre[maxn];
int Find(int x){return x==pre[x]?x:pre[x]=Find(pre[x]);}
void dfs(int u,int pre)
{fa[u]=pre;for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v==pre) continue;dfs(v,u);}
}
struct p
{ll a,b;int idx;bool operator<(const p& y) const{int op1=(a>=b),op2=(y.a>=y.b);if(op1==op2){if(b>a) return a>y.a;else return y.b>b;}return op1>op2;///优先考虑增益的}
};int main()
{int t;scanf("%d",&t);while(t--){scanf("%lld",&n);init();A[1]=B[1]=0;priority_queue<p> pq;for(int i=2;i<=n;i++){scanf("%lld%lld",&A[i],&B[i]);pq.push(p{A[i],B[i],i});}for(int i=2;i<=n;i++){scanf("%d%d",&a,&b);add(a,b),add(b,a);}for(int i=1;i<=n;i++) fa[i]=pre[i]=i;///并查集结构dfs(1,1);while(!pq.empty()){p tp=pq.top();pq.pop();ll a=tp.a,b=tp.b;int id=tp.idx;cout<<a<<" "<<b<<endl;if(id==1) continue;if(a!=A[id]||b!=B[id]) continue;if(a==0&&b==0) continue;int ty=Find(fa[id]);///if(ty==id) continue;pre[id]=ty;///并查集A[ty]+=max(0LL,A[id]-B[ty]);B[ty]=B[id]+max(0LL,B[ty]-A[id]);pq.push(p{A[ty],B[ty],ty});}printf("%lld\n",A[1]);}return 0;
}