梦中的勇士

有一天，我们的孙学长因为“训练过于辛苦”，敲着敲着代码就睡着了。睡梦中，孙学长成了拯救世界的勇士。
孙学长梦中的世界是这样的，n个交叉路口，为1,2,3，...，n，由n-1条双向道路连接着。我们的孙学长现在在交叉路口1，最初有X的血值。
除了孙学长现在所在的交叉路口1，每个交叉路口都有一个大怪兽，大怪兽没有复活的能力，所以被孙学长打败后该路口就没有怪兽了(嘎嘎)，
如果孙学长想要去第k个路口，他必须与这个路口的怪兽斗争。
在斗争中，孙学长会失去ai的血量，当他最终打败怪兽的时候，他会得到bi的血量(不要问问什么，因为这是他的梦，嘤嘤嘤)
我们的孙学长是超级厉害的，所以他一定会打败怪兽。但是，如果孙学长的血量变为负数(<0),他会感觉自己好low(啊哈哈哈)，所以我们的孙学长是不会让这种情况出现的！！！
当孙学长梦到自己像超人一样打败所有怪兽的时候，他被自己的猪队友敲键盘的声音吵醒了，孙学长很不开心，毕竟不是人人都可以当super hero。
为了“惩罚”他，孙学长把自己的梦告诉了他，要求他算出在梦中的自己血量不为负数的情况下，最初需要的血量X最少为多少。
孙学长的猪队友太猪了，机智的你能帮帮他的猪队友算出来吗？
(温馨提示，如果孙学长想去有道路连接的下一个路口，他必须先打败当前路口的怪兽~)

第一行一个数T(1<=T<=2000),表示测试样例的数量。
每一个测试样例中，第一行一个数字n(2<=n<=100000)表示交叉路口的数量。
接下来的n-1行，每行两个数字ai，bi(0<=ai,bi<=10^9),表示第2,3，...，n个路口打败怪兽失去的血量和得到的血量。
再接下来的n-1行，每行两个数字u和v，表示u和v路口之间有道路连接。
保证∑n≤10^6.

#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; friend bool operator <(const node & a ,const node &b) { if(a.x<a.y&&b.x<b.y) return a.x>b.x; if(a.y<=a.x&&b.y<=b.x) return a.y<b.y; return a.x>=a.y; } }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]]==1) return getfa(fa[x]); return fa[x]; } int main() { IO int T; cin>>T; while(T--) { int n;cin>>n; for(int i=2;i<=n;i++){ int x,y;cin>>x>>y; a[i]={x,y,i}; G[i].clear(); v[i]=0; q.push(a[i]); } G[1].clear();v[1]=0;fa[1]=1; a[1].x=a[1].y=a[1].id=0; for(int i=2;i<=n;i++){ int u,v;cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1,0); while(!q.empty()) { node c=q.top(); q.pop(); if(v[c.id]) continue; int ff=getfa(c.id); 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) q.push(a[ff]); v[c.id]=1; } cout<<a[1].x<<endl; } return 0; }

详情