• 原题链接

• 赛后重新想，不到十分钟就会了。感觉我是 zz。

本题解将通过链和特殊性质 A 两档部分分引导读者走向正解。请各位不要跳读。

链

我们首先来考虑链的部分分。

不难发现，这部分的关键是实现一个形如 check(x,l,r) 的函数，表示 $x$ 结点在 $[l,r]$ 这段时间的生长高度能否达成目标。同时，这也是正解的一个关键函数。

不妨列出 $x$ 结点高度的表达式：

先考虑 $c_x \geq 0$ 的情况，那么上式可按如下化简：

接下来考虑 $c_x<0$，此时我们不妨找到使得 $b_x + ic_x \geq 1$ 的最大的 $i$，不难得出：$i_{max} = \lfloor \frac{1-b_x}{c_x} \rfloor$。接下来分情况讨论，可得：

$h = \begin{cases}r-l+1 & i_{max} < l \\ b_x(r-l+1)+c_x\frac{(l+r)(r-l+1)}{2} & i_{max}> r \\b_x(i_{max}-l+1)+c_x\frac{(l+i_{max})(i_{max}-l+1)}{2}+r-i_{max} & i_{max} \in [l,r] \end{cases}$

至此这个函数实现完毕。而统计答案，你就对链上的第 $i$ 个点二分出最小的 $r$ 满足 check(i,i,r) 为真的 $r$，所有 $r$ 取个 $\max$ 即可。

特殊性质 A

接着我们思考特殊性质 A。

不难发现此时每个结点生长到目标高度所需时间与种下的时间无关，即有 $t_x = \lceil \frac{a_x}{b_x} \rceil$。

将结点按 $t_x$ 从大到小排序。考虑这样一个贪心，我们顺次考虑所有结点，若该结点已被种树就跳过，否则将根到该结点这条链按顺序把未种树的结点种树。显然这样做会得到一个种树顺序的序列，显然由于 $t_x$ 更小的结点不是时间的瓶颈，我们这样做是最优的。

实际实现过程中，我们标记一下每个结点是否种过树。当考虑当前结点 $x$ 时，暴力跳到最后一个未被标记的祖先结点，然后倒序再给每个结点赋上开始种树的时间 $s_x$。取 $s_x+t_x-1$ 的最大值即可。

正解

想明白了前两个部分，正解就是容易的。

考虑一般情况与特殊性质 A 的区别，不难发现我们无法得到上述的 $t_x$ 了，究其根本是因为树种下的时间会影响种树需要的时间。

我们考虑二分答案，并修改 $t_x$ 的定义为要使该结点合法的最晚种树时间。显然在该前提下，$t_x$ 可以用二分答案加上链部分所实现的函数求出。而这时我们按照 $t_x$ 从小到大考虑，不难发现问题就转化为了特殊性质 A 时的问题，套用以上做法即可解决。

时间复杂度 $O(n \log n \log v)$。用桶排并上二次函数相关知识应该能将 $\log n$ 去掉，不过没必要。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n, p[N], d[N], st[N];
LL a[N], b[N], c[N], t[N];
vector<int> G[N];
bool v[N];

__int128 F(__int128 i, __int128 l, __int128 r) {
    if(t[i] < l) return r - l + 1;
    if(t[i] > r) return (r - l + 1) * b[i] + (l + r) * (r - l + 1) / 2 * c[i];
    return (r - t[i] + 1) + (t[i] - l) * b[i] + (t[i] - 1 + l) * (t[i] - l) / 2 * c[i];  
}

void dfs(int x, int fa) {
    for(int y : G[x]) if(y != fa) {
        dfs(y, x);
        p[x] = min(p[x], p[y] - 1);
    }
} 

bool check(int ed) {
    for(int i=1; i<=n; i++) {
        if(F(i, 1, ed) < a[i]) return 0;
        int l=1, r=n;
        while(l < r) {
            int mid=(l + r + 1) >> 1;
            if(F(i, mid, ed) >= a[i]) l=mid;
            else r=mid - 1;
        }
        p[i] = l;
    }
    dfs(1, 0);
    memset(st, 0, sizeof(st));
    for(int i=1; i<=n; i++) {
        if(p[i] < 1) return 0;
        st[p[i]]++;
    }
    for(int i=1; i<=n; i++) {
        st[i] += st[i-1];
        if(st[i] > i) return 0;
    }
    return 1;
}

int main() {
    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] = 1e10;
        else t[i] = (1 - b[i] + c[i]) / c[i];
    }
    
    for(int i=1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int l = n, r = 1e9;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}