提交记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+2;
int n,l,r=1e9,m,f[N];
struct node{
	int a,b,c,x;
	vector<int>son;
}t[N];
int getf(int i){
	int a=t[i].a,b=t[i].b,c=t[i].c,x=t[i].x;
	unsigned int T;
	if(x>=m)
		T=(1+m)*m/2*c+m*b;
	else
		T=(1+x)*x/2*c+x*b+m-x;
	int L=0,R=m+1;
	while(L+1<R){
		int M=(L+R)>>1,tmp=M-1;
		unsigned int T2;
		if(x>=tmp)
			T2=(1+tmp)*tmp/2*c+tmp*b;
		else
			T2=(1+x)*x/2*c+x*b+tmp-x;
		if(T-T2>=a)
			L=M;
		else
			R=M;
	}
	return L;
}
void dfs(int u,int fa){
	f[u]=getf(u);
	for(int i=0;i<t[u].son.size();i++){
		int v=t[u].son[i];
		if(v==fa)
			continue;
		dfs(v,u);
		f[u]=min(f[u],f[v]-1);
	}
}
bool check(){
	dfs(1,0);
	sort(f+1,f+1+n);
	for(int i=1;i<=n;i++){
		if(f[i]<i)
			return 0;
	}
	return 1;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&t[i].a,&t[i].b,&t[i].c);
		int L=0,R=1e9+2;
		while(L+1<R){
			int M=(L+R)>>1;
			if(M*t[i].c+t[i].b>=1)
				L=M;
			else
				R=M;
		}
		t[i].x=L;
	}
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		t[x].son.push_back(y);
		t[y].son.push_back(x);
	}
	l=n-1;
	while(l+1<r){
		m=(l+r)>>1;
		if(check())
			r=m;
		else
			l=m;
	}
	printf("%lld",r);
	return 0;
}