rt，使用了__int128 不知道为什么全部MLE了

洛谷IDE自测正常

评测记录

# include <cstdio>
# include <algorithm>
# include <cstring>
# define _ __int128
# define int long long
using namespace std;
const int N = 1e5+10;
int n,lk[N],f[N],fa[N],id[N],hp,an;
_ a[N],b[N],c[N],d[N],t[N];
int read(){
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9'){
		if (ch == '-') f = -1;
		ch =  getchar();
	}
	while (ch >= '0' && ch <= '9'){
		x = (x<<1)+(x<<3)+(ch^48); ch = getchar();
	}
	return x*f;
}
_ write(_ x){
	if (x < 0) putchar('-'),x=-x;
	if (x > 9) write(x/10);
	putchar(x%10+'0');
}
struct sth{
	int ue,we;
}e[N*2];
void ad(int u,int v){
	e[++hp] = {v,lk[u]};
	lk[u] = hp;
}
void yu(int nw,int la){
	fa[nw] = la;
	for (int i = lk[nw]; i; i = e[i].we){
		if (e[i].ue != la) yu(e[i].ue,nw);
	}
}
bool ppp(int aa,int bb){
	return t[aa] < t[bb];
}
int fi(int x){
	if (f[x] || !x) return 0; f[x]  = 1;
	return fi(fa[x])+1;
}
bool chk(_ x){
	int l,r;
	for (int i = 1; i <= n; i++){
		l = 1,r = n;
		if (d[i] == -2){
			if (x * b[i] < a[i]) return false;
			t[i] = x-(a[i]-1)/b[i];
		}
		else if (d[i] == -1 || d[i] > x){
			if (x*b[i]+c[i]*x*(x+1)/2 < a[i]) return false;
			while (l < r){
				int mid = l+r+1 >> 1ll;
				if ((x-mid+1)*b[i]+c[i]*(mid+x)*(x-mid+1)/2 >= a[i]) l = mid;
				else r = mid-1;
			}
			t[i] = l;
		}
		else{
			if (x - d[i] + 1 >= a[i]){
				t[i] = x - a[i] + 1;
			}
			else{
				if ((d[i]-1)*b[i]+c[i]*d[i]*(d[i]-1)/2 < a[i]-(x-d[i]+1)) return false;
				l = 1; r = d[i]-1;
				while (l < r){
					int mid = l+r+1 >> 1ll;
					if ((d[i]-mid)*b[i]+c[i]*(d[i]+mid-1)*(d[i]-mid)/2 >= a[i]-(x-d[i]+1)) l = mid;
					else r = mid-1;
				}
				t[i] = l;
			}
		}
		id[i] = i;
	}
	sort(id+1,id+1+n,ppp); memset(f,0,sizeof(f));
	int cc,nw = 0;
	for (int i = 1; i <= n; i++){
		cc = fi(id[i]);  if (nw + cc > t[id[i]]) return false;
		nw += cc;
	}
	return true;
}
void ef(int l,int r){
	if (l >= r){
		an = r; return ;
	}
	int mid = l+r >> 1ll;
	if (chk(mid)) return ef(l,mid);
	return ef(mid+1,r);
}
signed main(){
	scanf("%lld",&n);
	for (int i = 1; i <= n; i++){
		a[i]=read();b[i]=read();c[i]=read();
	}
	int u,v;
	for (int i = 1; i < n; i++){
		u = read(); v = read();
		ad(u,v); ad(v,u);
	}
	yu(1,0);
	for (int i = 1; i <= n; i++){
		if (c[i] > 0) d[i] = -1;
		else if (c[i] < 0) d[i] = (b[i]-1)/(-c[i])+1; //第d[i]天变1 
		else d[i] = -2;
	}
	ef(n,1e9);
	write(an);
	return 0;
}