CSP-S2023 T4求助

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 10;

struct edge{
	int to, nxt;
}e[maxn];

int n, x, y, tot, k[maxn], dep[maxn], head[maxn];
ll a[maxn], b[maxn], c[maxn], q[maxn], rr[maxn], kk[maxn];
vector<int>g[maxn];

void add(int u, int v){
	e[++tot] = {v, head[u]};
	head[u] = tot;
}

void dfs(int u){
	rr[u] = kk[u];
	for(int i = head[u]; i; i = e[i].nxt){
		dfs(e[i].to);
		rr[u] = min(rr[u], rr[e[i].to]);
	}
}

void dfs1(int u, int fa){
	dep[u] = dep[fa] + 1;
	for(int v : g[u]){
		if(fa == v) continue;
		dfs1(v, u); add(u, v);
	}
}

bool cmp(int x, int y){
	if(rr[x] == rr[y]) return dep[x] < dep[y];
	return rr[x] < rr[y];
}

bool check(int i, int x, int tot){
	ll res = 0, all = tot - x + 1;
	if(!c[i]) res = all * b[i];
	else if(c[i] > 0) res = all * b[i] + (x + tot) * all / 2 * c[i];
	else{
		ll t = (b[i] - 1) / (-c[i]);
		if(t < x) res = all;
		else if(t >= tot) res = all * b[i] + (x + tot) * all / 2 * c[i];
		else{
			res = (t - x + 1) * b[i] + (x + t) * (t - x + 1) / 2 * c[i];
			res += tot - t;
		}
	}
	return res >= a[i];
}

bool CHECK(int MID){
	for(int i = 1; i <= n; i++){
		int l = 0, r = MID;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(check(i, mid, MID)) l = mid;
			else r = mid - 1; 
		}
		if(!l) return 0;
		kk[i] = l;
	}
	dfs(1); sort(q + 2, q + n + 1, cmp);
	for(int i = 1; i <= n; i++) if(kk[q[i]] < i) return 0; 
	return 1;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n; 
	for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
	for(int i = 1; i < n; i++){
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	} 
	dfs1(1, 0); for(int i = 1; i <= n; i++) q[i] = i;
	int L = 1, R = 1e9;
	while(L < R){
		int MID = L + R >> 1;
		if(CHECK(MID)) R = MID;
		else L = MID + 1;
	}
	cout << L << endl;
	return 0;
}