记录编号	587808	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2023S]种树	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	8.814 s
提交时间	2024-05-04 10:38:54	内存使用	9.42 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define __ __int128
#define in inline
#define re register
#define F(i,a,b) for(re int i = a;i <= b;i++) 
#define D(i,a,b) for(re int i = a;i >= b;i--)
const int N = 1e5+10;


ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}


ll n;
ll a[N],b[N],c[N],t[N];
int fa[N];
struct made{
    int ver,nx;
}e[N<<2];
int hd[N],tot;
void add(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
void dfs(int x){
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y == fa[x])continue;
        fa[y] = x;dfs(y);
    }
}


in __ calc(int i,__ l,__ r){//__int128 是真脑残 
    if(c[i] >= 0)return (r-l+1) * b[i] + (r-l+1) * (l+r) / 2 * c[i];
    __ M = (1-b[i])/c[i];
    if(r < M)return (r-l+1) * b[i] + (r-l+1) * (l+r) / 2 * c[i];
    if(l > M)return (r-l+1);
    return r - M + (M-l+1) * b[i] + (M-l+1) * (l+M) / 2 * c[i];
}

bool v[N];int id[N],st[N],top;
bool check(int M){
    F(i,1,n){
        if(calc(i,1,M) < a[i])return 0;
        int l = 1,r = n;
        while(l < r){//二分最晚种树时间 
            int mid = l + r + 1 >> 1;
            if(calc(i,mid,M) >= a[i])l = mid;
            else r = mid-1;
        }
        t[i] = l,id[i] = i;
    }
    // 
    memset(v,0,sizeof v);
    sort(id+1,id+1+n,[](int x,int y){return t[x] < t[y];});
    int tim = 0,top = 0;
    F(i,1,n){//树上遍历 
        int x = id[i];
        while(!v[x])v[x] = 1,st[++top] = x,x = fa[x];
        while(top){if(t[st[top]] < ++tim)return 0;top--;}
    }
    return 1;
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n = read();
    F(i,1,n)a[i] = read(),b[i] = read(),c[i] = read();
    F(i,1,n-1){
        int x,y;x = read(),y = read(); 
        add(x,y),add(y,x);
    }
    dfs(1);fa[1] = 1;
    ll l = 0,r = 1e9;
    while(l < r){//二分答案 
        ll mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid+1;
    }
    printf("%lld\n",l);
    
    return 0;
    
}