#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l,i##end=r;i<i##end;++i)
#define Rs(i,l,r) for(int i=l,i##end=r;i>i##end;--i)
#define Le(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define Re(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define L(i,l) for(int i=0,i##end=l;i<i##end;++i)
#define E(i,l) for(int i=1,i##end=l;i<=i##end;++i)
#define W(t) while(t--)
#define Wh while

const int N=25,M=2*N,inf=1e9,K=100010;
int n,h[N],e[M],ne[M],idx,b[K],c[K],res=inf;
ll a[K];
// int path[N]{0,1};//don't forget memset h!
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int calc(ll x,ll a,ll b,ll c){
	// cout<<x<<' '<<a<<' '<<b<<' '<<c<<'\n';
	/*
	head:b+cx
	c>=0 b+cx,b+c(x+1),b+c(x+2),...,b+c*mid,等差数列求和即可
	c<0 b+tc>0     tc > -b    t < -b/c(ceil)
	
	she t=-b/c
		day < t    等差数列求和即可
		day>=t 前t-1项+(day-(t-1))
	*/
	ll head=b+c*x;
	if(head<1)return x+a-1;
	ll t=c<0?(b+(-c-1))/-c:-1,l=x,r=inf;
	__int128 fr=((__int128)t-x)*(head+b+c*(t-1))>>1;
	if(~t&&fr<=a)
		return t-1+a-fr;
	ll front=fr;
	Wh(l<r){
		__int128 mid=l+r>>1,res;
		if(c>=0||mid<t)res=(mid-x+1)*(b+b+c*(x+mid))>>1;
		else res=front+mid-t+1;
		if(res>=a)r=mid;
		else l=mid+1;
	}
	return r;
}
bool st[N]{0,1};
void output(vector<int>&A){
	// cout<<"len="<<A.size()<<'\n';
	// for(auto v:A)cout<<v<<' ';
	// cout<<'\n';
}
void dfs(int d,vector<int>&A,int ans){
	// output(A);
	if(ans>res)return;
	if(d==n+1){
		res=ans;
		// E(i, n)cout<<path[i]<<' ';
		// cout<<'\n';
		return;
	}
	vector<int>nex=A;
	for(int x:A){
		// path[d]=x;
		st[x]=1;
		ans=max(ans,calc(d,a[x],b[x],c[x]));
		nex.erase(find(nex.begin(),nex.end(),x));
		int cnt=0;
		Ed{
			int j=e[i];
			if(!st[j]){
				nex.push_back(j);
				++cnt;
			}
		}
		dfs(d+1,nex,ans);
		st[x]=0;
		Wh(cnt--)nex.pop_back();
		nex.push_back(x);
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	#endif
	#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#endif
	// cout<<calc(1,12,1,1)<<'\n';
	// return 0;
	cin>>n;
	E(i, n)cin>>a[i]>>b[i]>>c[i],n<=20&&(h[i]=-1);
	if(n<=20){
		E(i, n-1){
			int a,b;
			cin>>a>>b;
			add(a,b),add(b,a);
		}
		// cout<<ne[4]<<'\n';
		// return 0;
		vector<int>init;
		int x=1;
		Ed{
			int j=e[i];
			init.push_back(j);
		}
		dfs(2,init,calc(1,a[1],b[1],c[1]));
		cout<<res<<'\n';
		return 0;
	}
	res=0;
	E(i, n)res=max(res,calc(i,a[i],b[i],c[i]));
	cout<<res<<'\n';
	return 0;
}

以上代码是暴力+链，但是在洛谷上对于1~4的点会TLE两个，请问有没有什么更快的写法？