与众不同的95pt-#3

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
const ll Max = 1e9+10;
int n;
ll a[N], b[N], c[N], l[N];
struct node
{
    ll x, v;//
}d[N];
bool cmp(node a, node b){
    return a.v<b.v;
}
ll t[N];
int head[N], k;
int u, v;
int fa[N];
struct edge
{
    int next;
    int to;
}edge[2*N];
void charu(int u, int v)
{
    k++;
    edge[k].to = v;
    edge[k].next = head[u];
    head[u] = k;
}
void solve(int i, ll ans)
{
    ll l=1, r=n;
    d[i].v = -1ll;
    while(l<=r)
    {
        ll mid = (l+r)>>1;//枚举mid，求出mid~ans时间这棵树的生长高度能否满足要求
        __int128 sum = 0, p = 1;

        if(c[i]>=0){//此时高度为单调递增的一次函数
            sum = p * (ans-mid+1) * b[i];
            sum += p * (ans-mid+1)*(ans+mid)*c[i]/2;
        }
        else{
            if(mid>=t[i])
                sum = ans-mid+1;
            else if (ans>t[i])
                sum = p*(t[i]-mid+1)*b[i]
                    + p*(t[i]-mid+1)*(t[i]+mid)*c[i]/2
                    + ans-t[i];
            else //mid<ans<=t[i]
                sum = p * (ans-mid+1)*b[i]
                    + p * (ans-mid+1)*(ans+mid)*c[i]/2;
        }
        if(p*a[i]<=sum){
            d[i].v = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    return;
}
bool vis[N];
bool check(ll mid)
{
    for (int i=1;i<=n;++i){
        d[i].x = i;
        solve(i, mid);//求出第i个地区截止到mid为止满足高度>=a[i]时i地区最晚种树的时间
        l[i] = d[i].v;
        if(d[i].v<=0) return false;
    }
    memset(vis, 0, sizeof(vis));
    vis[0] = 1;
    sort (d+1, d+n+1, cmp);
    ll h = 0;
    for (int i=1;i<=n;++i){
        stack<int> s;
        ll u = d[i].x;
        while(!vis[u]){
            s.push(u);
            vis[s.top()] = 1;
            u = fa[u];
        }
        while(!s.empty()){
            ++h;
            if(l[s.top()]<h) return 0;
            s.pop();
        }
    }
    return 1;
}
void dfs(int u, int f)
{
    for(int i=head[u];i;i=edge[i].next){
        int v = edge[i].to;
        if(v==f) continue;
        fa[v] = u;
        dfs(v, u);
    }
}
int main()
{
    //freopen("tree3.in", "r", stdin);
    scanf("%d", &n);
    for (int i=1;i<=n;++i){
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
        if(c[i]<0)
            t[i] = (1ll-b[i])/c[i];//当天数 day>t[i]时函数值固定为1
    }
    for (int i=1;i<n;++i){
        scanf("%d%d", &u, &v);
        charu(u, v);
        charu(v, u);
    }
    dfs(1, 1);
    ll l=1, r = Max, ans = 0;
    while(l<=r){
        ll mid = (l+r)>>1;
        //cout << mid << endl;
        if(check(mid))
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    printf("%lld\n", ans);
    return 0;
}