马蜂良好，悬赏本号永久关注

思路：二分套二分，先二分答案，再二分求出每个位置最多可以从什么时候开始仍能长到目标高度。之后再dfs处理一下求出每个点的时间限制，判断是否可行

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,cnt[N];
int h[N],e[M],ne[M],idx;
struct Nd{
	ll a,b,c;
}w[N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
ll tim[N];
ll get_time(ll T,int x){
	ll L=1,R=T,ans;
	ll b=w[x].b,c=w[x].c;
	while(L<=R){
		int mid=L+R>>1;
		if(c>=0){
			ll h1=(T-mid+1)*b+c*(T+mid)*(T-mid+1)/2ll;
			if(h1>=w[x].a) L=mid+1,ans=mid;
			else R=mid-1;
		} 
		else{
			ll t1=(b-1)/-c;
			ll h0=(t1>=mid?(t1-mid+1)*b+c*(t1+mid)*(t1-mid+1)/2ll+T-t1:T-mid+1);
			if(h0>=w[x].a) L=mid+1,ans=mid;
			else R=mid-1;   
		}
	}
	return ans;
}
void dfs(int u,int fa){
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa) continue;
		dfs(j,u);
		tim[u]=min(tim[u],tim[j]-1); 
	}
}
bool check(ll T){
	for(int i=1;i<=n;i++) tim[i]=get_time(T,i);
	dfs(1,-1);
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++){
		if(tim[i]<1) return 0;
		cnt[tim[i]]++;
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=cnt[i];
		if(sum>i) return 0;
	}
	return 1;
}
signed main(){
	memset(h,-1,sizeof(h));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld%lld",&w[i].a,&w[i].b,&w[i].c);
	int u,v;
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	ll L=n,R=1e9,ans;
	while(L<=R){
		int mid=L+R>>1;
		if(check(mid)) ans=mid,R=mid-1;
		else L=mid+1;
	}
	printf("%lld",ans);
	return 0;
}