rt,luogu $O(n \log^2 V)$ 被卡常，憋屈致死，下面优化成了桶排，但是上面等差数列求和实在斗不动了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
i128 read(){
	i128 x = 0,ch = getchar(),f = 1;
	while(ch < 48 || ch > 57){
		if(ch == '-')f = -1;
		ch = getchar();
	}
	while(ch >= 48 && ch <= 57)x = x * 10 + ch - 48,ch = getchar();
	return x * f;
}

const int MX = 1e5 + 7;

int n;
i128 a[MX],b[MX],c[MX],t[MX];
vector<int > g[MX];
i128 ansmax = 1000000000;

//b,c,天数为d
i128 calc(i128 b,i128 c,i128 d){
	//cerr << (int)b << ' ' << (int)c << '\n';
	if(c < 0){
		i128 zero = (1 - b) / c;
		if((1 - b) % c == 0)zero--;
		i128 ret = 0,d0 = min(d,zero);
		//cerr << "d0 = " << (int)d0 << '\n';
		ret += (b + c + b + d0 * c) * d0 / 2;
		ret += d - d0;
		return ret;
	}
	return (b + c + b + c * d) * d / 2;
}
//a,b,c的树最晚要啥时候踩上去
i128 days(i128 a,i128 b,i128 c,i128 T){
	i128 l = 1,r = min(ansmax,T),ans = 0,tot = calc(b,c,T);
	while(l <= r){
		i128 mid = l + r >> 1;
		if(tot - calc(b,c,mid - 1) >= a){ans = mid,l = mid + 1;}
		else r = mid - 1;
	}
	return ans;
}

bool vis[MX];int fa[MX];

void dfs(int x,int f){
	fa[x] = f;
	for(int i = 0;i < g[x].size();i++){
		int to = g[x][i];
		if(to == f)continue;
		dfs(to,x);
	}
}

struct st{
	int id;
	i128 t;
}s[MX];

st mk(int id,i128 t){
	st ret;
	ret.id = id;ret.t = t;
	return ret;
}

vector<st > buc[MX];

bool cmp(st x,st y){return x.t < y.t;}

bool check(i128 T){
	for(int i = 1;i <= n;i++)t[i] = days(a[i],b[i],c[i],T);
	//cerr << "cur ending = " << (int)T << '\n';
	//cerr << "days : \n";
	//for(int i = 1;i <= n;i++)cout << (int)t[i] << ' ';
	//cout << '\n';
	for(int i = 1;i <= n;i++){buc[i].clear();buc[i].resize(0);}
	for(int i = 1;i <= n;i++)
		if(t[i] == 0)return false;
		else if(t[i] <= n)buc[t[i]].push_back(mk(i,t[i]));
	int tot = 0;
	for(int i = 0;i <= n;i++)
		for(int j = 0;j < buc[i].size();j++)s[++tot] = buc[i][j];
	memset(vis,false,sizeof(vis));
	int d = 1;
	//cerr << "start\n";
	for(int k = 1;k <= tot;k++){
		int i = s[k].id;
		if(vis[i])continue;
		vector<int > grand;
		grand.push_back(i);
		while(fa[i] != 0 && !vis[fa[i]]){
			grand.push_back(fa[i]);
			i = fa[i];
		}
		for(int j = grand.size() - 1;j >= 0;j--){
			//cerr << "col node " << grand[j] << '\n';
			if(t[grand[j]] < d)return false;
			vis[grand[j]] = true;
			d++;
		}
	}
	return true;
}

int main(){
	n = read();
	for(int i = 1;i <= n;i++){a[i] = read();b[i] = read();c[i] = read();}
	for(int i = 1;i < n;i++){
		int u = read();int v = read();
		g[u].push_back(v);g[v].push_back(u);
	}
	//cout << "node 4 : \n";
	//for(int i = 1;i <= 6;i++)cout << (int)calc(b[4],c[4],i) << ' ';
	//cerr << '\n';
	
	dfs(1,0);
	int l = 1,r = 1000000000,ans = 0;
	while(l <= r){
		int mid = l + r >> 1;
		if(check(mid)){ans = mid,r = mid - 1;}
		else l = mid + 1;
	}
	cout << ans << '\n';
	
	return 0;
}