悬关

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 1e5 + 10;

inline int read()
{
    int x = 0, fl = 1; char ch = getchar();
    while (!isdigit(ch)) { if(ch == '-') fl = -1; ch = getchar(); }
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * fl;
}
inline void write (int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar (x % 10 + 48);
}

int n, t[MAXN]; int a[MAXN], b[MAXN], c[MAXN];
struct _Edge { int to, nxt; }_e[MAXN << 1]; int _head[MAXN], _cnt;
inline void _add (int u, int v) { _e[++ _cnt] = (_Edge){v, _head[u]}, _head[u] = _cnt; }
inline int when (int i)
{
    if (c[i] >= 0) return 1e9 + 1;
    int l = 1, r = 1e9 + 1, mid;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (b[i] + c[i] * mid >= 1) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
inline void input()
{
    n = read();
    for (int i = 1; i <= n; ++ i)
        a[i] = read(), b[i] = read(), c[i] = read(), t[i] = when(i);
    for (int i = 1, u, v; i < n; ++ i)
        u = read(), v = read(), _add(u, v), _add(v, u);
}

struct Edge { int to, nxt; }e[MAXN]; int head[MAXN], cnt;
inline void add (int u, int v) { e[++ cnt] = (Edge){v, head[u]}, head[u] = cnt; }
void dfs_init (int u, int fa)
{
    for (int i = _head[u], v; i; i = _e[i].nxt)
    {
        if ((v = _e[i].to) == fa) continue;
        add(v, u), dfs_init(v, u);
    }
}
inline void init() { dfs_init(1, -1); }

struct Node { int id, val; }minn[MAXN];
bool flag[MAXN]; int ans;
inline bool _check (int i, int ti, __int128 ti_max)
{
    if (ti_max < t[i]) return (b[i] * (ti_max - ti + 1) + c[i] * ((ti + ti_max) * (ti_max - ti + 1) / 2) >= a[i]);
    if (ti >= t[i]) return (ti_max - ti + 1 >= a[i]);
    return ((ti_max - t[i] + 1) + b[i] * (t[i] - ti) + c[i] * (ti + (t[i] - 1)) * (t[i] - ti) / 2 >= a[i]);
}
inline bool Dich (int i, int time)
{
    int l = 0, r = time, mid;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (_check(i, mid, time)) l = mid + 1;
        else r = mid - 1;
    }
    if (r == 0) return false;
    return minn[i].val = r, minn[i].id = i, true;
}
inline bool cmp (Node x, Node y) { return x.val < y.val; }
bool dfs (int u, int res, int _id)
{
    if (u == 1 and !flag[u]) ++ res, flag[u] = true;
    if (flag[u])
    {
        if (res <= minn[_id].val) return true;
        else return false;
    }
    for (int i = head[u], v; i; i = e[i].nxt)
    {
        bool _flag = dfs(v = e[i].to, res + 1, _id);
        flag[v] = true;
        return _flag;
    }
}
inline bool check (int time)
{
    for (int i = 1; i <= n; ++ i)
        if (!Dich(i, time)) return false;
        else flag[i] = false;
    sort (minn + 1, minn + n + 1, cmp);
    for (int i = 1; i <= n; ++ i)
        if (!dfs(minn[i].id, 0, i)) return false;
    return true;
}
inline void work()
{
    int l = 1, r = 1e9, mid;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    ans = l;
}

inline void output() { write(ans), putchar('\n'); }

signed main()
{
    input();
    init();
    work();
    output();
    return 0;
}

调了很久，不保证不是什么 NT 错误（wtcl