95分求助，看了几个帖子，机房场切大佬没调出

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,a[N],b[N],c[N],d[N],h[N],tot,fa[N],p[N],cnt;
struct node{
	int id,day;
	inline bool operator < (const node &X)const{
		return day<X.day;
	}
}mx[N];
struct edge{int v,ne;}e[N<<1];
inline void add(int u,int v){
	e[++tot]={v,h[u]},h[u]=tot;
}
void dfs(int u){
	for(int v,i=h[u];i;i=e[i].ne){
		v=e[i].v;
		if(v==fa[u])continue;
		fa[v]=u,dfs(v);
	}
}
inline int find(int i,__int128 x){
	int l=1,r=x,mid,ret=-1;
	if(!d[i]){
		while(l<=r){
			mid=l+r>>1;
			if(b[i]*(x-mid+1)+c[i]*(x-mid+1)*(x+mid)/2>=a[i])
				l=mid+1,ret=mid;
			else r=mid-1;
		}
	}
	else{
		while(l<=r){
			mid=l+r>>1;
			if(mid>=d[i]){
				if(x-mid+1>=a[i])
					l=mid+1,ret=mid;
				else r=mid-1;
			}
			else{
				if(x-d[i]+1+b[i]*(d[i]-mid)+(__int128)c[i]*(d[i]-mid)*(mid+d[i]-1)/2>=a[i])
					l=mid+1,ret=mid;
				else r=mid-1;
			}
		}
	}
	return ret;
}
void add(int u){
	if(!u||p[u])return;
	add(fa[u]);
	p[u]=++cnt;
}
inline bool check(int x){
	cnt=0;
	for(int i=1;i<=n;++i){
		mx[i]={i,find(i,x)},p[i]=0;
		if(!~mx[i].day)return 0;
	}
	sort(mx+1,mx+n+1);
	for(int id,i=1;i<=n;++i){
		id=mx[i].id;
		if(!p[id])add(id);
		if(p[id]>mx[i].day)return 0;
	}
	return 1;
}
inline int Ceil(int x,int y){return x/y+(x%y!=0);}
signed main(){
	// freopen("tree.in","r",stdin);
	// freopen("tree.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i]>>c[i];
		if(c[i]<0)d[i]=Ceil(b[i]-1,-c[i]);
	}
	for(int u,v,i=1;i<n;++i){
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	dfs(1);
	int l=0,r=1e9,mid,ans=0;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid))
			r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<endl;
	return 0;
}