CSP-S T4

#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define lll __int128
using namespace std;
const int N = 1e5 + 5;

int n, fa[N], id[N], buc[N], tim[N];
ll a[N], b[N], c[N], val[N];
int tp, stk[N];
vector<int> G[N];

void dfs(int u) {
	for (auto v : G[u])
		if (fa[u] != v) fa[v] = u, dfs(v);
}

lll calc(int id, int st, ll tot) {
	if (b[id] + c[id] * st <= 1) return tot - st + 1;
	if (c[id] >= 0) return (lll)b[id] * (tot - st + 1) + (lll)c[id] * (st + tot) * (tot - st + 1) / 2;
	ll t = (b[id] - 1) / (-c[id]);
	if (t >= tot) return (lll)b[id] * (tot - st + 1) + (lll)c[id] * (st + tot) * (tot - st + 1) / 2;;
	return (lll)b[id] * (t - st + 1) + (lll)c[id] * (st + t) * (t - st + 1) / 2 + tot - t;
}

bool check(ll mid) {
	for (int i = 1; i <= n; i++) buc[i] = tim[i] = 0;
	for (int i = 1; i <= n; i++) {
		int l = 1, r = n, res = 0;
		while (l <= r) {
			int Mid = l + r >> 1;
			if (calc(i, Mid, mid) >= a[i]) res = Mid, l = Mid + 1;
			else r = Mid - 1;
		}
		val[i] = res;
		buc[val[i]]++;
	}
	for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
	for (int i = n; i; i--) id[buc[val[i]]--] = i;
	for (int i = 1, j = 1; i <= n; i++) {
		int u = id[i];
		if (tim[u]) continue;
		tp = 0;
		while (u && !tim[u]) stk[++tp] = u, u = fa[u];
		while (tp) tim[stk[tp--]] = j++;
	}
	for (int i = 1; i <= n; i++)
		if (tim[i] > val[i]) return false;
	return true;
}

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