Process exited after 1.591 seconds with return value 3221225725 请按任意键继续. . .
#include <bits/stdc++.h>
#define MAXN 100010
#define i128 __int128
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int vis[MAXN],fa[MAXN],date[MAXN];
int n,u,v;
vector<int> p[MAXN];
int read()
{
char ch=getchar();
int f=1; int s=0;
while(ch=='-')
{
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return f*s;
}
struct node
{
int a,b,c;
int id;
int x,date;
}a[MAXN];
bool cmp(node a,node b)
{
return a.date<b.date;
}
bool check(i128 mid,i128 x,int i)
{
if(a[i].c>=0) return (a[i].b+mid*a[i].c+a[i].b+x*a[i].c)*(mid-x+1)>=2*a[i].a;
else if(a[i].c<0)
{
if(x>=a[i].x) return (mid-x+1)>=a[i].a;
else if(a[i].x<=mid) return (a[i].x-x)*(a[i].b+x*a[i].c+a[i].b+(a[i].x-1)*a[i].c)+2*(mid-a[i].x+1)>=2*a[i].a;
else return (a[i].b+x*a[i].c+a[i].b+mid*a[i].c)*(mid-x+1)>=2*a[i].a;
}
}
void dfsfa(int x,int fat)
{
fa[x]=fat;
for(int i=0;i<p[x].size();i++)
if(p[x][i]!=fat)
dfsfa(p[x][i],x);
}
bool check2(int mid)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
int l=1,r=mid,ans=-1;
while(l<=r)
{
int midd=l+r>>1;
if(check(mid,midd,i)) l=midd+1,ans=midd;
else r=midd-1;
}
if(ans==-1) return 0;
a[i].date=ans;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
date[a[i].id]=a[i].date;
int time=1; vis[1]=1;
for(int i=1;i<=n;i++)
{
if(vis[a[i].id]) continue;
vector< pair<int,int> > tmp;
int j=a[i].id; tmp.push_back({j,date[j]});
j=fa[j];
while(!vis[j])
{
tmp.push_back({j,date[j]});
j=fa[j];
}
//reverse(tmp.begin(),tmp.end());
for(int k=tmp.size()-1;k>=0;k--)
{
if(time+1>tmp[k].se) return 0;
time++;
vis[tmp[k].fi]=1;
}
}
return 1;
}
signed main()
{
freopen("tree4.in","r",stdin);
ios::sync_with_stdio(0);
n=read();
for(int i=1;i<=n;i++)
{
a[i].a=read();a[i].b=read();a[i].c=read(); a[i].id=i;
if(a[i].c<0) a[i].x=ceil((1-a[i].b)*1.0/a[i].c);
}
for(int i=1;i<n;i++)
{
u=read();v=read();
p[u].push_back(v);
p[v].push_back(u);
}
dfsfa(1,0);
int L=1,R=1000000000,ans=-1;
while(L<=R)
{
int mid=L+R>>1;
if(check2(mid)) ans=mid,R=mid-1;
else L=mid+1;
}
printf("%lld",ans);
return 0;
}