提高组T4

#include<bits/stdc++.h>
using namespace std;
int n,u,v,l,r;
long long a[100005],b[100005],c[100005],d[100005],minn[100005],ans,cnt;
vector<int>g[100005];
bool vis[100005];
bool checkp(int st,int i,int ed){
	if(b[i]+c[i]*ed>=1||c[i]>=0)
		return c[i]*(1ll*(ed+st)*(ed-st+1)/2)+b[i]*(ed-st+1)>=a[i];
	int s=b[i]/(-c[i]);
	if(b[i]%(-c[i])==0)
		s--;
	return b[i]*(s-st+1)+c[i]*(1ll*(s+st)*(s-st+1)/2)+ed-s>=a[i];
}
long long get(int i,long long sum){
	long long l=1,r=1e5,ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(checkp(mid,i,sum))
			ans=mid,l=mid+1;
		else
			r=mid-1;
	}
	return ans;
}
struct node{
	int x,idx;
	bool operator<(const node t)const{
		return x>t.x;
	}
};
void dfs(int u,int fa=-1){
	minn[u]=d[u];
	for(auto &&v:g[u])
		if(v!=fa){
			dfs(v,u);
			minn[u]=min(minn[u],minn[v]);
		}
}
bool check(long long sum){
	cnt=0;
	memset(vis,false,sizeof vis);
	memset(minn,0x3f,sizeof minn);
	for(int i=1;i<=n;i++)
		d[i]=get(i,sum);
	dfs(1);
	priority_queue<node>q;
	q.push({1,1});
	vis[1]=true;
	while(!q.empty()){
		node cur=q.top();
		q.pop();
		cnt++;
		if(cur.x<cnt)
			return false;
		for(auto &&v:g[cur.idx])
			if(!vis[v])
				q.push({minn[v],v}),vis[v]=true;
	}
	return true;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld%lld",a+i,b+i,c+i);
	for(int i=1;i<n;i++)
		scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
	l=1,r=1000000007;
	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;
}