求助75分错因

#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("Ofast")
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair((a),(b))
#define int __int128

const int maxn=5e5+10;
const int inf=1e12;
const int mod=1e9+7;
int n,m,k,ans;
int a[maxn],b[maxn],c[maxn],id[maxn];
int t[maxn],h[maxn],vis[maxn],fa[maxn];

vector<int> g[maxn];

inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
	return s*w;
}

inline void write(int x) {
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar('0'+x%10);
}

inline void dfs(int u) {
	for(int v:g[u]) {
		if(v==fa[u]) continue;
		fa[v]=u;
		dfs(v);
	}
}

inline int f(int x,int l,int r) {
	if(r<l) return 0;
	if(l>t[x]) return r-l+1;
	if(r<t[x]) return b[x]*(r-l+1)+c[x]*((l+r)*(r-l+1)/2);
	return b[x]*(t[x]-l+1)+c[x]*(l+t[x])*((t[x]-l+1)/2)+r-t[x];
}

inline int geth(int p,int end) {
	int dl=1,dr=n,dmid,tot=1;
	while(dl<=dr) {
		dmid=(dl+dr)>>1;
		if(f(p,dmid,end)>=a[p]) dl=dmid+1,tot=dmid;
		else dr=dmid-1;
	}
	return tot;
}

stack<int> st;
inline bool check(int x) {
	for(int i=1;i<=n;++i)
		if(f(i,1,x)<a[i]) return false;
	for(int i=1;i<=n;++i) 
		h[i]=geth(i,x),id[i]=i;
	sort(id+1,id+n+1,[](int x,int y){return h[x]<h[y];});
	for(int i=1;i<=n;++i)
		vis[i]=0;
	vis[0]=1;
	int i,dfn=0;
	for(int e=1;e<=n;++e) {
		i=id[e];
		while(!vis[i]) {
			vis[i]=1;
			st.push(i);
			i=fa[i];
		}
		while(!st.empty()) {
			dfn++;
			int top=st.top();
			if(h[top]<dfn) return false;
			st.pop();
		}
	}
	return true;
}

signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i) {
		a[i]=read();
		b[i]=read();
		c[i]=read();
		if(c[i]<0) t[i]=(1-b[i])/c[i];
		else t[i]=inf;
	}
	for(int i=1;i<n;++i) {
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	int l=1,r=1e9,mid;
	while(l<=r) {
		mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	write(ans);
	return 0;
}