数据

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define test cerr << "test\n"
#define print(x) cerr << #x << " = " << x << '\n'
#define ll __int128

const int N = 1e5 + 5;
int n, a[N], b[N], c[N];
struct Edge { int to, nxt; } e[N << 1];
int cur, head[N];
void Add(int u, int v) { e[++cur] = {v, head[u]}; head[u] = cur; }
#define Go(u, v) for (int i = head[u], v; v = e[i].to, i; i = e[i].nxt)

ll f(ll i, ll l, ll r) { return (l > r) ? 0 : (ll)(r - l + 1) * b[i] + (ll)(l + r) * (r - l + 1) / 2 * (ll)c[i]; }
ll calc(int i, int l, int r) {
	if (c[i] >= 0) return f(i, l, r);
	else {
		int k = min(r, (b[i] - 1) / (-c[i]));
		return (k <= l) ? r - l + 1 : f(i, l, k) + r - k;
	}
}
int t[N], cnt[N];
void dfs(int u, int fa) {
	Go(u, v) if (v != fa)
		dfs(v, u), t[u] = min(t[u], t[v] - 1);
}
bool check(int x) {
	t[1] = 1; cnt[1] = 0;
	for (int i = 2; i <= n; i++) {
		cnt[i] = 0;
		int l = 0, r = n, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (calc(i, mid, x) >= a[i]) l = mid + 1, ans = mid;
			else r = mid - 1;
		}
		t[i] = ans;
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		if (t[i] <= 0) return false;
		cnt[t[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		cnt[i] += cnt[i - 1];
		if (cnt[i] > i) return false;
	}
	return true;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		Add(u, v); Add(v, u);
	}
	int l = n, r = 1e9, ans = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	cout << ans;
	return 0;
}