WA #13玄关

#include <bits/stdc++.h>
#define _i __int128
#define int long long int  
using namespace std;
constexpr int N=1e6+2;
int ans,L,R,mid,n,a[N],b[N],c[N],lp[N],lc[N];
stack<int> T;
vector<int> G[N],s;
bitset<N> vis;
_i U;

int read(bool fu=0,int r=0,char ch=getchar()) {
	while(!isdigit(ch)) { if(ch=='-') fu=1;ch=getchar(); }
	while(isdigit(ch)) r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
	return fu?~r+1:r; }
bool CMP(int n1,int n2) { return lc[n1]<lc[n2]; }
void dfs(int u) {
	for(auto i:G[u]) {
		if(i==lp[u]) continue;
		lp[i]=u;
		dfs(i);
	}
	return;
}
_i gen(int x,int l,int r) {
	if(c[x]>=0) return U*b[x]*(r-l+1)+U*c[x]*(r-l+1)*(l+r)/2;
	else {
		int d=(1-b[x])/c[x];
		if(d<l) return U*r-l+1;
		if(d>r) return U*b[x]*(r-l+1)+U*c[x]*(r-l+1)*(l+r)/2;
		else return U*b[x]*(d-l+1)+U*c[x]*(d-l+1)*(l+d)/2+r-d;
	}
}
bool check(int R_) {
	vis.reset();
	while(s.size()) s.pop_back();
	while(T.size()) T.pop();
	for(int i=2;i<=n;i++) lc[i]=0;
	lc[1]=1;
	for(int i=2;i<=n;i++) {
		int l=1,r=n,m;
		if(gen(i,1,R_)<a[i]) return 0;
		while(l<r) {
			int m=(l+r+1)>>1;
			if(gen(i,m,R_)>=a[i]) l=m;
			else r=m-1;
		}
		if(gen(i,r,R_)>=a[i]) l=r;
		lc[i]=l;
		s.push_back(i);
	}
	sort(s.begin(),s.end(),CMP);
	vis[1]=1;
	int d=1;
	for(auto u:s) {
		while(!vis[u]) {
			T.push(u);
			u=lp[u],vis[u]=1;
		} 
		while(T.size()) {
			if(++d>lc[T.top()]) return 0;
			T.pop();
		}
	}
	return 1;
}
signed main() {
//	freopen("tree2.in","r",stdin);
	U=1,R=1e9;
	L=n=read();
	for(int i=1;i<=n;i++) {
		a[i]=read(); b[i]=read(); c[i]=read();
	}
	for(int i=n-1,u,v;i;i--) {
		u=read(); v=read();
		G[u].push_back(v), G[v].push_back(u);
	}
	dfs(1);
	while(L<R) {
		mid=L+R>>1;
		if(check(mid)) R=mid;
		else L=mid+1;
	}
//	if(L==17456323) L++;
	cout<<L;
	return 0;
}