改了 n 天,实在调不出来力(恼
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int max(int a,int b){
return a>b?a:b;
}
int min(int a,int b){
return a<b?a:b;
}
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
return;
}
int n,i,a[100001],b[100001],c[100001],t[100001],f[100001],head[100001],sum,u,v;
bool vis[100001];
struct node{
int fa,to,nxt;
};
node e[200000];
struct no{
int t,num;
};
no nod[100001];
void add(int a,int b){
e[++sum].fa=a;
e[sum].to=b;
e[sum].nxt=head[a];
head[a]=sum;
}
void dfs(int u,int fa){
f[u]=fa;
int i;
for(i=head[u];i;i=e[i].nxt){
if(e[i].to!=fa){
dfs(e[i].to,u);
}
}
}
int s(int u,int l,int r){
if(c[u]>=0){
return (r-l+1)*b[u]+(r-l+1)*(l+r)/2*c[u];
}
int tmp=(1-b[u])/c[u];
if(tmp<l){
return r-l+1;
}
if(tmp>r){
return (r-l+1)*b[u]+(r-l+1)*(l+r)/2*c[u];
}
return (tmp-l+1)*b[u]+(tmp-l+1)*(l+tmp)/2*c[u]+r-tmp;
}
bool cmp(no a,no b){
return a.t<b.t;
}
bool check(int r){
int i;
for(i=1;i<=n;i++){
if(s(i,1,r)<a[i]){
return 0;
}
int l=1,rr=n,mid;
while(l<rr){
mid=(l+r+1)/2;
if(s(i,mid,r)>=a[i]){
l=mid;
}
else{
r=mid-1;
}
}
nod[i].t=l;
nod[i].num=i;
vis[i]=0;
}
sort(nod+1,nod+n+1,cmp);
int x=0;
for(i=1;i<=n;i++){
int now=nod[i].num;
stack<int> q;
while(!vis[now]){
vis[now]=1;
q.push(now);
now=f[now];
}
while(!q.empty()){
int tmp=q.top();
q.pop();
if(nod[tmp].t<++x){
return 0;
}
}
}
return 1;
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();
for(i=1;i<=n;i++){
a[i]=read();
b[i]=read();
c[i]=read();
}
for(i=1;i<n;i++){
u=read();
v=read();
add(u,v);
add(v,u);
}
dfs(1,0);
vis[0]=1;
int l=n,r=1000000000,mid;
while(l<r){
mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
write(l);
return 0;
}