5183 - NOIP CSP 2023 提高: 第四题 种树（tree）
你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。 森林的地图有 n 片地块，其中 1 号地块连接森林的入口。共有 n − 1 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。 你的目标是：在每片地块上均种植一棵树木，并使得 i 号地块上的树的高度生长到不低于 ai 米。 你每天可以选择一个未种树且 .与 .某 .个 .已 .种 .树 .的 .地 .块 .直 .接 .邻 .接（ .即 .通 .过 .单 .条 .道 .路 .相.连）的地块，种一棵高度为 0 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 1 天你只能在 1 号空地种树。 对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 x 天，i 号地块上的树会长高 max(bi + x ∗ ci, 1) 米。注意这里的 x 是从整个任务的第一天，而非种下这棵树的第一天开始计算。 你想知道：最少需要多少天能够完成你的任务？
输入
输入的第一行包含一个正整数 n，表示森林的地块数量。 接下来 n 行：每行包含三个整数 ai, bi, ci，分别描述一片地块，含义如题目描述中所述。 接下来 n − 1 行：每行包含两个正整数 ui, vi，表示一条连接地块 ui 和 vi 的道路。
输出
输出一行仅包含一个正整数，表示完成任务所需的最少天数
样例
输入
4 12 1 1 2 4 -1 10 3 0 7 10 -2 1 2 1 3 3 4
输出
5
输入
20 610287562490950674 885730665 524863980 6465154937106138 125644983 10 25526148 86884815 -418052299 4878566359808986 698467722 -50 4346217306420974 456748134 -24 410451661036151236 866022801 555949789 296430095754312 185435049 -58 25779019751029177 231358373 61 9670756993083570 595829152 -17 4315527612211042 663464035 -51 491863418024590758 831492683 908994741 289608171371 741754234 -946354 3787649516665471 596690387 -47 153131564671460 118693977 -46 23449898939524909 842083576 6 3090236853189311 593538639 -57 8771118861034472 458481025 -9 218318672355843 169759989 -66 17642088181721776 155088413 42 558461780136236367 876432411 670504574 3 2 19 3 9 4 17 5 20 6 10 7 12 8 12 9 19 10 1 11 1 12 19 13 10 14 11 15 15 16 16 17 16 18 9 19 13 20
输出
25526156
提示
【样例 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 米
