45pts 求调

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
ll n, a[100005], b[100005], c[100005], mx = 0, w[100005], hea[100005], p[100005], tot = 0;
struct Edge{
    ll next, to;
} edge[200005];
void add(ll a, ll b){
    edge[++tot] = Edge{hea[a], b};
    hea[a] = tot;
    return ;
}
void dfs(ll now, ll fa){
    for (ll i = hea[now]; i; i = edge[i].next){
        ll v = edge[i].to;
        if (v == fa){
            continue;
        }
        dfs(v, now);
        w[now] = min(w[now], w[v] - 1);
    }
    return ;
}
bool flg = 0;
bool check(ll x){
    for (ll i = 1; i <= n; i++){
        if (c[i] == 0){
            w[i] = x - ceil(a[i] * 1.0 / b[i]) + 1;
        }else if (c[i] > 0){
            __int128 l = 1, r = n, ans = 0;
            while (l <= r){
                __int128 mid = (l + r) / 2;
                __int128 wx = b[i] * (x - mid + 1) + (x - mid + 1) * (mid + x) / 2 * c[i];
                if (wx >= a[i]){
                    ans = mid;
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            w[i] = (ll)(ans);
        }else{
            __int128 l = 1, r = 1e18, wei = ceil((b[i] - 1) * 1.0 / (-c[i])) - 1, ans;
            __int128 tot = (x - wei);
            if (tot >= a[i]){
                w[i] = x - a[i] + 1;
            }else{
                l = 1, r = wei;
                if (n < r) r = n;
                while (l <= r){
                    __int128 mid = (l + r) / 2;
                    __int128 wx = tot + (wei - mid + 1) * b[i] + (mid + wei) * (wei - mid + 1) / 2 * c[i];
                    if (wx > a[i]){
                        ans = mid;
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
                w[i] = (ll)(ans);
            }
        }
    }
    dfs(1, -1);
    sort(w + 1, w + n + 1);
    for (ll i = 1; i <= n; i++){
        if (w[i] < i){
            return false; 
        }
    }
    return true;
}
int main(){
    //freopen("P9755_2.in", "r", stdin);
    cin >> n;
    for (ll i = 1; i <= n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    for (ll i = 1; i <= n - 1; i++){
        ll u, v;
        cin >> u >> v;
        add(u, v);
    }
    ll l = 1, r = 1e9, ans = -1;
    while (l <= r){
        ll mid = (l + r) / 2;
        if (check(mid)){
            ans = mid;
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}