萌新求助常数问题

#include <bits/stdc++.h>

#define N 100005
#define mod 998244353
#define LL long long
#define rep(i,l,r) for (int i=(l); i<=(r); ++i)
#define per(i,r,l) for (int i=(r); i>=(l); --i)


using namespace std;


struct EDGE {
	LL v, n;
} edge[N<<1];

struct node {
	LL id, nd;
	bool operator < (const node &A) const { return nd > A.nd ; }
} f[N];

LL n, u, v, cnt_edge, sz[N], h[N];
vector <LL> son[N];
LL a[N], b[N], c[N], up[N];

LL getsum (LL i, LL st, LL x) {
	if (x < st) return 0;
	if ((c[i] && ((LL)1e18 / c[i] / (st+x) / (x-st+1) == 0)) || ((LL)1e18 / (x-st+1) / b[i] == 0)) return -1;
	return 1ll * (x-st+1) * b[i] + 1ll * (st+x) * (x-st+1) / 2 * c[i];
}

bool cmp (LL x, LL y) {
	return f[x].nd < f[y].nd;
}

void build (LL u, LL v) {
	edge[++cnt_edge] = (EDGE) {v, h[u]};
	h[u] = cnt_edge; return ;
}

void dfs (int u, int fa) {
	for (int i=h[u]; i; i=edge[i].n) {
		int v = edge[i].v;
		if (v == fa) continue ;
		son[u].push_back (v);
		dfs (v, u); ++sz[u];
	} return ;
}

void DP (int u, int fa) {
	for (int i=h[u]; i; i=edge[i].n) {
		int v = edge[i].v;
		if (v == fa) continue ;
		DP (v, u);
	}
	sort (son[u].begin (), son[u].end (), cmp);
	for (int i=0; i<sz[u]; ++i) {
		f[u].nd = min (f[u].nd, f[son[u][i]].nd - i - 1);
	} 
	return ;
}

bool check (LL x) {
	rep (i, 1, n) {
		if (up[i] == -1 || x < up[i]) {
			if (getsum (i, 1, x) < a[i] && getsum (i, 1, x) != -1) return false;
			LL l = 1, r = x; f[i].nd = 1;
			while (l <= r) {
				LL mid = (l + r) >> 1, sm = getsum (i, mid, x);
				if (sm >= a[i] || sm == -1) l = mid+1, f[i].nd = mid;
				else r = mid-1;
			}
		}
		else {
			if (x - up[i] + 1 >= a[i]) { f[i].nd = x - a[i] + 1; continue ; }
			if (getsum (i, 1, up[i]-1) + (x-up[i]+1) < a[i] && getsum (i, 1, up[i]-1) != -1) return false;
			LL l = 1, r = up[i]-1; f[i].nd = 1;
			while (l <= r) {
				LL mid = (l + r) >> 1, sm = getsum (i, mid, up[i]-1);
				if (sm == -1 || sm + (x-up[i]+1) >= a[i]) l = mid+1, f[i].nd = mid;
				else r = mid-1;
			}
		}
		if (f[i].nd < 1) return false;
	}
	DP (1, 0);
	priority_queue <node> q;
	int T = 1;
	q.push (f[1]);
	for (; !q.empty (); ++T) {
		node fro = q.top (); q.pop ();
		if (T > fro.nd) return false;
		for (int i=0; i<sz[fro.id]; ++i) {
			q.push (f[son[fro.id][i]]);
		}
	}
	return true;
}

LL findans (LL l = 1, LL r = (LL)1e9) {
	LL ans = r;
	while (l <= r) {
		LL mid = (l + r) >> 1;
		if (check (mid)) r = mid-1, ans = mid;
		else l = mid+1;
	}
	return ans;
}

int main () {
	scanf ("%lld", &n);
	rep (i, 1, n) {
		scanf ("%lld%lld%lld", &a[i], &b[i], &c[i]);
		f[i].id = i;
		if (c[i] >= 0) up[i] = -1;
		else {
			if (abs (1-b[i]) % abs (c[i]) == 0) up[i] = abs (1-b[i]) / abs (c[i]);
			else up[i] = ceil ((double)(1-b[i]) / c[i]);
			if (up[i] <= 0) up[i] = 1;
		}
	}
//	rep (i, 1, n) printf ("%lld ", up[i]); 
	rep (i, 1, n-1) {
		scanf ("%lld%lld", &u, &v);
		build (u, v); build (v, u);
	}
	dfs (1, 0);
	printf ("%lld\n", findans ());
	return 0;
}