悬关，CSP-S T4 25pts求调

#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
template< typename T > inline void read(T &x){
	char c1=getchar();x=0;int f=0;
	for(;!isdigit(c1);c1=getchar()) f|=(c1=='-');
	for(;isdigit(c1);c1=getchar()) x=((x<<3)+(x<<1)+(c1^48));
	x=f?-x:x;
}
template< typename T > inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=100005;
const int INF=1000000000;
int n,tot,s[N];
bool flag;
ll a[N],b[N],c[N],d[N];
int h[N],nx[N<<1],to[N<<1];
bool cmp(int x,int y){
	return d[x]<d[y];
}
il void add(int u,int v){
	nx[++tot]=h[u];
	h[u]=tot;
	to[tot]=v;
}
ll calc(int u,int p){
	if(c[u]>=0) return (((b[u]<<1)+(p+1)*c[u])*p)>>1;
	else {
		ll x=(b[u]-1)/(-c[u]);
		if(p<=x) {
			return (((b[u]<<1)+(p+1)*c[u])*p)>>1;
		}
		else {
			return ((((b[u]<<1)+(x+1)*c[u])*x)>>1)+p-x;
		}
	}
}
void query(int u,int p){
	int l=1,r=p;
	while(l<r){
		int mid =(l+r+1)>> 1;
		if(calc(u,p)-calc(u,mid-1)>=a[u]){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	d[u]=l;
}
void dfs(int u,int f){
	for(int i=h[u],v;i;i=nx[i]){
		v=to[i];
		if(v==f) continue;
		dfs(v,u);
		d[u]=min(d[u],d[v]-1);
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]),read(b[i]),read(c[i]);
	}
	for(int i=1,u,v;i<n;i++){
		read(u),read(v);
		add(u,v);
		add(v,u);
	}
	int l=1,r=INF,mid;
	while(l<r){
		mid=(l+r)>>1;
		flag=1;
		for(int i=1;i<=n;i++){
			s[i]=i;
			query(i,mid);
		}
		dfs(1,0);
		sort(s+1,s+n+1,cmp);
		for(int i=1;i<=n;i++){
			if(d[s[i]]<i) {
				flag=0;
				break;
			}
		}
		if(flag) r=mid;
		else l=mid+1;
	}
	write(l);
	return 0;
}