问题 D: [CSP-S 2023] 种树

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：5 解决：3

你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。

森林的地图有 $n$ 片地块，其中 $1$ 号地块连接森林的入口。共有 $n - 1$ 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。

你的目标是：在每片地块上均种植一棵树木，并使得 $i$ 号地块上的树的高度生长到不低于 $a_{i}$ 米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相连）的地块，种一棵高度为 $0$ 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 $1$ 天你只能在 $1$ 号空地种树。

对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 $x$ 天， $i$ 号地块上的树会长高 $\max (b_{i} + x \times c_{i}, 1)$ 米。注意这里的 $x$ 是从整个任务的第一天，而非种下这棵树的第一天开始计算。

你想知道：最少需要多少天能够完成你的任务？

说明/提示

【样例 1 解释】

第 $1$ 天：在地块 $1$ 种树，地块 $1$ 的树木长高至 $2$ 米。

第 $2$ 天：在地块 $3$ 种树，地块 $1, 3$ 的树木分别长高至 $5, 3$ 米。

第 $3$ 天：在地块 $4$ 种树，地块 $1, 3, 4$ 的树木分别长高至 $9, 6, 4$ 米。

第 $4$ 天：在地块 $2$ 种树，地块 $1, 2, 3, 4$ 的树木分别长高至 $14, 1, 9, 6$ 米。

第 $5$ 天：地块 $1, 2, 3, 4$ 的树木分别长高至 $20, 2, 12, 7$ 米。

【样例 2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

【样例 3】

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

【样例 4】

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

【数据范围】

对于所有测试数据有： $1 \leq n \leq 1 0^{5}, 1 \leq a_{i} \leq 1 0^{18}, 1 \leq b_{i} \leq 1 0^{9}, 0 \leq ∣ c_{i} ∣ \leq 1 0^{9}, 1 \leq u_{i}, v_{i} \leq n$ 。保证存在方案能在 $1 0^{9}$ 天内完成任务。

特殊性质 A：对于所有 $1 \leq i \leq n$ ，均有 $c_{i} = 0$ ；

特殊性质 B：对于所有 $1 \leq i < n$ ，均有 $u_{i} = i$ 、 $v_{i} = i + 1$ ；

特殊性质 C：与任何地块直接相连的道路均不超过 $2$ 条；

特殊性质 D：对于所有 $1 \leq i < n$ ，均有 $u_{i} = 1$ 。

输入的第一行包含一个正整数 $n$ ，表示森林的地块数量。

接下来 $n$ 行：每行包含三个整数 $a_{i}, b_{i}, c_{i}$ ，分别描述一片地块，含义如题目描述中所述。

接下来 $n - 1$ 行：每行包含两个正整数 $u_{i}, v_{i}$ ，表示一条连接地块 $u_{i}$ 和 $v_{i}$ 的道路。

输出一行仅包含一个正整数，表示完成任务所需的最少天数。

问题 D: [CSP-S 2023] 种树

题目描述

说明/提示

输入

输出

样例输入复制

样例输出复制

问题 D: [CSP-S 2023] 种树

题目描述

说明/提示

输入

输出

样例输入 复制

样例输出 复制

样例输入复制

样例输出复制