最后一题 tree 

玄学做法能得几分
#include<bits/stdc++.h>
typedef long long ll;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i) 
#define pii pair<ll,ll>
using namespace std;
ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(ll x){
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar('0'+x%10);
}
const ll N=1e5+5;
ll n,a[N],b[N],c[N],fa[N],tim[N],nt[N],ft[N],del[N],dep[N],tag[N],flB=1,flD=1,ddeg[N],flC=1,bel[N],deg[N];
vector<ll>to[N],es[N]; 
ll find(ll x){
	return ft[x]==x?x:ft[x]=find(ft[x]);
}
void merge(ll x,ll y){
	ll fx=find(x),fy=find(y);
	if(fx!=fy)ft[fx]=fy;
}
void dfs(ll x,ll f){
	fa[x]=f;
	dep[x]=dep[f]+1;
	for(ll y:to[x]){
		if(y==f)continue;
		dfs(y,x);
	}
}
multiset<pii>s;
ll calc(ll l,ll r){
	return (r+l)*(r-l+1)/2;
}
void adde(ll x,ll y){
	ddeg[y]++;
	es[x].push_back(y);
//	cout<<x<<" "<<y<<endl;
}
ll chk(ll mid){
	rep(i,1,n){
		ll l=1,r=mid;
		nt[i]=0;
		while(l<=r){
			ll qq=(l+r)>>1;
			__int128 ret=0;
			if(c[i]>=0)ret=b[i]*(mid-qq+1)+(__int128)c[i]*calc(qq,mid);
			else {
				ll p=min(tim[i],mid);
				if(p>=qq)ret=b[i]*(p-qq+1)+(__int128)c[i]*calc(qq,p);
				ret+=max(0ll,mid-max(qq,p+1)+1);
			}
			if(ret>=(__int128)a[i])nt[i]=qq,l=qq+1;
			else r=qq-1;
		}
		if(!nt[i])return 0;
	}
	if(flB){
		rep(i,1,n){
			if(nt[i]<i)return 0;
		}
		return 1;
	} 
	if(flD){
		sort(nt+2,nt+n+1);
		rep(i,1,n){
			if(nt[i]<i)return 0;
		} 
		return 1;
	}
	if(flC){
		rep(i,1,n)ft[i]=i;
		rep(i,2,n){
			if(fa[i]!=1)merge(i,fa[i]);
		}
		ll lfp=to[1][0];
		ll rgp=0;
		if(deg[1]==2)rgp=to[1][1];
		ll cnt0=0,cnt1=0;
		rep(i,2,n){
			if(find(i)==find(lfp))bel[i]=0,cnt0++;
			else bel[i]=1,cnt1++;
		}
		rep(i,1,n)ddeg[i]=0,es[i].clear();
		rep(i,2,n){
			ll u=nt[i]-dep[i];
			if(u<0)return 0;
			if(bel[i]==0){
				u=min(cnt1,u);
				if(u!=cnt1)adde(dep[i]-1,u+cnt0+1);
			}
			else {
				u=min(cnt0,u);
				if(u!=cnt0)adde(dep[i]-1+cnt0,u+1);
			}
		}
		queue<ll>q;
	//	cout<<"oonanguodahuoyu "<<mid<<"\n";
		rep(i,2,n){
			if(!ddeg[i])q.push(i);
		}
		ll cntt=0;
		while(!q.empty()){
			cntt++;
			ll u=q.front();q.pop();
			for(ll v:es[u]){
				ddeg[v]--;
				if(ddeg[v]==0)q.push(v);
			}
		}
		if(cntt==n-1)return 1;
		return 0;
	}
	return 0;
}
namespace solA{
	ll timm[25][25],popc[(1<<20)+5];
	ll dp[(1<<20)+5];
	void solve(){
		rep(i,1,n){
			rep(j,1,n){
				//i-th point planted at j minimum time
				timm[i][j]=(ll)1e9+1;
				ll l=j,r=1e9;
				while(l<=r){
					ll mid=(l+r)>>1;
					__int128 ret=0;
					if(c[i]>=0)ret=b[i]*(mid-j+1)+(__int128)c[i]*calc(j,mid);
					else {
						ll p=min(tim[i],mid);
						if(p>=j)ret=b[i]*(p-j+1)+(__int128)c[i]*calc(j,p);
						ret+=max(0ll,mid-max(j,p+1)+1);
					}
					if(ret>=(__int128)a[i])timm[i][j]=mid,r=mid-1;
					else l=mid+1;
				}
			}
		}
		rep(i,0,(1<<n))dp[i]=1e9+1;
		rep(i,1,(1<<n)-1)popc[i]=popc[i-(i&(-i))]+1;
		dp[0]=0;
		rep(i,0,(1<<n)-1){
			ll c=popc[i];
			rep(j,1,n){
				if((i>>(j-1))&1)continue;
				if(((i>>(fa[j]-1))&1)==0&&j>1)continue;
				dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],max(dp[i],timm[j][c+1]));
			}
		}
		write(dp[(1<<n)-1]);
		putchar('\n');
	}
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();
	rep(i,1,n)a[i]=read(),b[i]=read(),c[i]=read();
	rep(i,2,n){
		ll x=read(),y=read();
		to[x].push_back(y);
		to[y].push_back(x);
		flD&=(x==1);
		flB&=(x==i-1&&y==i);
		deg[x]++,deg[y]++;
	}
	rep(i,1,n)flC&=(deg[i]<=2);
	dfs(1,0);
	rep(i,1,n){
		ll l=0,r=(ll)(1e9);
		if(c[i]>=0)continue;
		while(l<=r){
			ll mid=(l+r)>>1;
			if(b[i]+c[i]*mid>=1)tim[i]=mid,l=mid+1;
			else r=mid-1;
		}
	}if(n<=20){
		solA::solve();
		return 0;
	}
	ll l=n,r=(ll)1e9,res=1e9;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(chk(mid))res=mid,r=mid-1;
		else l=mid+1;
	}
	write(res);
	return 0;
}