rt，WA on #15 & #18。

#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int maxn = 1e5 + 5;

int n;
ull a[maxn], b[maxn], c[maxn];
int head[maxn], nxt[maxn << 1], to[maxn << 1], cnt = 0, fa[maxn];
int t[maxn], vis[maxn], ord[maxn];
stack<int> s;

void add(int u, int v){
	nxt[++ cnt] = head[u];
	to[cnt] = v;
	head[u] = cnt;
}
bool get(int x, __int128 l, __int128 r){
	if(c[x] >= 0) return (r - l + 1) * b[x] + (l + r) * (r - l + 1) / 2 * c[x] >= a[x];
	__int128 maxi = (1 - b[x]) / c[x];
	if(maxi < l) return r - l + 1 >= a[x];
	else if(maxi > r) return (r - l + 1) * b[x] + (l + r) * (r - l + 1) / 2 * c[x] >= a[x];
	return (maxi - l + 1) * b[x] + (l + maxi) * (maxi - l + 1) / 2 * c[x] + r - maxi >= a[x];
}
void dfs(int x, int f){
	if(x != f) fa[x] = f;
	for(int i = head[x]; i; i = nxt[i]){
		int j = to[i];
		if(j == f) continue;
		dfs(j, x);
	}
}
bool cmp(int x, int y){
	return t[x] < t[y];
}
bool check(int k){
	for(int i = 1; i <= n; i ++){
		if(!get(i, 1, k)) return false;
		int l = 0, r = n, ans;
		while(l <= r){
			int mid = l + r >> 1;
			if(get(i, mid, k)){
				l = mid + 1;
				ans = mid;
			}else{
				r = mid - 1;
			}
		}
		t[i] = ans;
		vis[i] = 0;
		ord[i] = i;
	}
	sort(ord + 1, ord + n + 1, cmp);
	vis[0] = 1;
	int tim = 0;
	while(!s.empty()) s.pop();
	for(int i = 1; i <= n; i ++){
		int x = ord[i];
		while(!vis[x]){
			s.push(x);
			vis[x] = 1;
			x = fa[x];
		}
		bool fl = false;
		while(!s.empty()){
			x = s.top();
			s.pop();
			tim ++;
			if(tim > t[x]) return false;
		}
	}
	return true;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%llu %llu %llu", &a[i], &b[i], &c[i]);
	}
	for(int i = 1; i < n; i ++){
		int u, v;
		scanf("%d %d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 1);
	int l = 0, r = 1e9, ans;
	while(l <= r){
		int mid = l + r >> 1;
		if(check(mid)){
			r = mid - 1;
			ans = mid;
		}else{
			l = mid + 1;
		}
	}
	printf("%d", ans);
	return 0;
}

调了快两小时了。

第一遍写完电脑死机了，又写了一遍，结果一直没过，救我