考虑二分，对于每一个节点处理出一个最慢的选择时间，对其排序，跟着选就行了
反正我考场上是没有想出来这个东西，所以这里来详细的证明一下
对于一对点 \(x,y\)，不难发现有一些性质
- 无论先选哪一个，总用时都是相同的，选完之后树的形态是相同的
- 想要选这两个点中的一个，都必须先选 \(lca(x,y)\) 到根的路径，所以选择的顺序对后选的那一个的花费时间是没有影响的
- 考虑设 \(x\) 的截止时间小于 \(y\)，假设一定有解，若先选 \(x\) 超时，那一定是 \(y\) 超时了，否则与假设不符，如果 \(y\) 超时，那不难发现一定无解，因为反过来给 \(x\) 分配更长的时间更容易趋势
所以考虑排序，然后做就行了
复杂度 \(O(n\log{n}\log{V})\)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define fp(a,b,c) for(int a=(int)b;i<=(int)c;++a)
#define fd(a,b,c) for(int a=(int)b;i>=(int)c;--a)
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define fir first
#define sec second
#define mpr make_pair
#define ll long long
#define i128 __int128_t
#define met(x,y) memset(x,y,sizeof(x))
#define int ll
using namespace std;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=(ch^'-')?1:-1,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;}
const int N=1e5+10;
int n;
int a[N],b[N],c[N],fa[N],tp[N],pp[N],tim[N];
int last[N],ord[N],vis[N];
vector<int> g[N];
void dfs(int now,int f){
fa[now]=f;for(int x:g[now]) if(x^f) dfs(x,now);
}
i128 C2(ll l,ll r){
if(r<l) return 0;
return (i128)(r+l)*(r-l+1)/2;
}
i128 ccalc(int l,int r,int id){
i128 pu=(i128)(C2(l,r)*c[id]+b[id]*(r-l+1));
return pu;
}
ll calc(int st,int ed,int id){
i128 r=0;
if(pp[id]>=st&&pp[id]<=ed){
if(tp[id]==1){
r+=ed-pp[id]+1;
if(st<pp[id]) r+=ccalc(st,pp[id]-1,id);
}else {
r+=pp[id]-st+1;
if(ed>pp[id]) r+=ccalc(pp[id]+1,ed,id);
}
}
else if(pp[id]<=ed&&tp[id]==1){
r=ed-st+1;
}
else r=ccalc(st,ed,id);
return (ll)min((i128)1e18,r);
}
int bs(int lim,int id){
int l=1,r=lim,ans=-1;
while(l<=r){
int mid(l+r>>1);
if(calc(mid,lim,id)>=a[id])
ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
bool check(int lim){
fp(i,1,n){
tim[i]=bs(lim,i);
if(tim[i]==-1) return false;
}
iota(ord+1,ord+n+1,1);
sort(ord+1,ord+n+1,[&](int x,int y){return tim[x]<tim[y];});
int T=0;
met(vis,0);
fp(i,1,n){
int now=ord[i];
while(now&&!vis[now])++T,vis[now]=1,now=fa[now];
if(T>tim[ord[i]]) return false;
}
return true;
}
int cel(int x,int y){
if(x%y==0) return x/y;
return x/y+1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=rd();
fp(i,1,n)
a[i]=rd(),b[i]=rd(),c[i]=rd();
fp(i,1,n){
if(c[i]<0)
tp[i]=1,pp[i]=cel(-b[i],c[i]);
if(b[i]<=0){
if(!c[i]) tp[i]=2,pp[i]=0;
else tp[i]=2,pp[i]=-b[i]/c[i];
}
}
fp(i,1,n-1){
int u=rd(),v=rd();
g[u].emplace_back(v),
g[v].emplace_back(u);
}
dfs(1,0);
int l=n,r=1e9,ans=n;
while(l<=r){
int mid(l+r>>1);
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout << ans << endl;
return 0;
}