思路与算法

把最终完成日期记为 $D$。若树 $u$ 在第 $p$ 天种植，它在 $D$ 天结束时的高度为 $G_u(D)-G_u(p-1)$，其中 $G_u(t)=\sum_{x=1}^t\max(b_u+c_ux,1)$。日增长始终为正，所以满足要求的种植日期构成前缀 $1\ldots L_u$。截止日只需截到 $n$，因为全部 $n$ 次种植可以连续完成，提前种植不会变差。

当 $c\ge0$，$G(t)=bt+ct(t+1)/2$；当 $c<0$，令 $z=\min(t,\lfloor(b-1)/(-c)\rfloor)$，有 $G(t)=bz+cz(z+1)/2+t-z$。反解 $G(p-1)\le G(D)-a$ 得到截止日。参考程序用稳定根式估计反解位置，再以128位整数精确比较相邻位置并校正，最终判定不依赖浮点近似。

树以1为根，种植次序必须父亲先于孩子。后序把截止日收紧为 $d_u=\min(L_u,\min_{v\text{为孩子}}(d_v-1))$。若有非正值，直接失败。其余截止日在 $1\ldots n$，计数排序后检查第 $j$ 个任务的截止日不小于 $j$。对 $D$ 在 $[n,10^9]$ 二分，返回最早可行日期。

正确性说明

首先，正日增长说明将种植提前不减少最终高度，因此每棵树可以等价替换为一个单位工时、截止日为 $L_u$ 的任务。任何合法种植次序中，父任务至少比每个孩子早一天；从叶向根归纳可知其实际日期必不超过收紧后的 $d_u$，所以收紧是必要的。

反过来，每条父子边都有 $d_{parent}<d_{child}$。按收紧截止日从小到大种植，父亲严格排在孩子前面，树的邻接种植规则因而满足。单位任务存在按时排程当且仅当按截止日排序后的第 $j$ 个截止日至少为 $j$：必要性来自前 $j$ 个任务的时间容量，充分性由直接按序安排第 $j$ 天给出。程序的计数累计判据与此相同。因此判定充要。更晚的结束日不减少任何树的高度，可行性单调，二分得到最优日期。

复杂度

建树、迭代求父子顺序与初始化数组共 $O(n)$ 时间、$O(n)$ 空间。题目给定整数范围内，增长求和、根式初值及精确相邻校正为常数次128位运算；一次判定含每点截止日、后序收紧、计数排序，共 $O(n)$。答案二分至多30次，总时间 $O(n\log 10^9)$，额外空间 $O(n)$。参考程序不递归遍历树，可处理满规模链。

易错点

种下当天已经生长，且 $x$ 是任务开始后的全局天数；不能写成树龄。负斜率降到1后继续以1生长，不能让高度下降。总和中间量可超过64位，需先转换到128位再乘。结束日期至少为 $n$，根只能最先种植，子节点的截止日会反向约束祖先。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
struct Plant {
    long long need, b, c;
    i128 prefix(long long t) const {
        if (t <= 0)
            return 0;
        if (c >= 0)
            return (i128)b * t + (i128)c * t * (t + 1) / 2;
        long long d = -c, z = min(t, (b - 1) / d);
        return (i128)b * z - (i128)d * z * (z + 1) / 2 + t - z;
    }
    int deadline(int days, int n) const {
        i128 target = prefix(days) - need;
        if (target < 0)
            return 0;
        if (prefix(n - 1) <= target)
            return n;
        long long z;
        if (c == 0)
            z = (long long)(target / b);
        else if (c > 0) {
            long double B = (long double)b + (long double)c / 2;
            long double C = (long double)target;
            z = (long long)(2 * C / (B + sqrtl(B * B + 2 * c * C)));
        } else {
            long long d = -c, pivot = (b - 1) / d;
            i128 at = prefix(pivot);
            if (target >= at)
                z = pivot + (long long)(target - at);
            else {
                long double B = (long double)b - (long double)d / 2;
                long double C = (long double)target;
                z = (long long)(2 * C / (B + sqrtl(max((long double)0, B * B - 2 * d * C))));
            }
        }
        z = max(0LL, min((long long)n - 1, z));
        while (z > 0 && prefix(z) > target)
            --z;
        while (z + 1 < n && prefix(z + 1) <= target)
            ++z;
        return (int)z + 1;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n))
        return 0;
    vector<Plant> a(n);
    for (auto &x : a)
        cin >> x.need >> x.b >> x.c;
    vector<vector<int>> g(n);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> parent(n, -1), order(1, 0);
    parent[0] = 0;
    for (size_t j = 0; j < order.size(); j++)
        for (int v : g[order[j]])
            if (v != parent[order[j]]) {
                parent[v] = order[j];
                order.push_back(v);
            }
    vector<int> d(n), count(n + 1);
    auto feasible = [&](int days) {
        if (days < n)
            return false;
        fill(count.begin(), count.end(), 0);
        for (int i = 0; i < n; i++) {
            d[i] = a[i].deadline(days, n);
            if (!d[i])
                return false;
        }
        for (int i = n - 1; i > 0; i--) {
            int u = order[i];
            d[parent[u]] = min(d[parent[u]], d[u] - 1);
        }
        for (int x : d) {
            if (x <= 0)
                return false;
            ++count[x];
        }
        int used = 0;
        for (int i = 1; i <= n; i++) {
            used += count[i];
            if (used > i)
                return false;
        }
        return true;
    };
    int lo = n, hi = 1000000000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    cout << lo << '\n';
}