求卡常

#include<bits/stdc++.h>
#define int long long
#define ll __int128
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
int n,tot,fa[N],t[N],vis[N];
ll a[N],b[N],c[N];
vector<int>v[N];
void dfs(int x,int lst){
	fa[x]=lst;
	for(auto it:v[x])if(it!=lst)dfs(it,x);
	return;
}
inline int F(int x,int mid){
	int lt=0,rt=mid+1;
	while(lt+1<rt){
		ll md=lt+rt>>1,T;
		if(!c[x])T=b[x]*(mid-md+1);
		else if(c[x]>=0)T=b[x]*(mid-md+1)+c[x]*(md+mid)*(mid-md+1)/2;
		else{
			int tx=b[x],ty=-c[x];
			int num=(tx+ty-1)/ty;
			if(md>=num)T=mid-md+1;
			else if(mid<num)T=b[x]*(mid-md+1)+c[x]*(md+mid)*(mid-md+1)/2;
			else T=b[x]*(num-md)+c[x]*(md+num-1)*(num-md)/2+(mid-num+1);
		}
		if(T>=a[x])lt=md;
		else rt=md;
	}
	return lt;
}
bool check(int mid){
	for(int i=2;i<=n;i++){
		t[i]=F(i,mid);
		if(t[i]<=1)return 0;
	}
	vector<pii>v;
	for(int i=2;i<=n;i++)v.push_back({t[i],i});
	sort(v.begin(),v.end()),tot=1;
	memset(vis,0,sizeof(vis)),vis[1]=1;
	for(int i=0;i<v.size();i++){
		int tmp=0,now=v[i].se;
		while(!vis[now])tmp++,vis[now]=1,now=fa[now];
		if(tot+tmp>v[i].fi)return 0;
		tot+=tmp;
	}
	return 1;
} 
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');return;
}
signed main(){
	// freopen("tree.in","r",stdin);
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=read(),c[i]=read();
	for(int i=1,x,y;i<n;i++){
		x=read(),y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	int lt=0,rt=1e9+1;
	while(lt+1<rt){
		int mid=lt+rt>>1;
		if(check(mid))rt=mid;
		else lt=mid;
	}
	write(rt);
	return 0;
}