{"problem":{"name":"[CSP-S 2023] 种树","description":{"content":"你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。 森林的地图有 $n$ 片地块，其中 $1$ 号地块连接森林的入口。共有 $n-1$ 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。 你的目标是：在每片地块上均种植一棵树木，并使得 $i$ 号地块上的树的高度生长到不低于 $a_i$ 米。 你每天可以选择一","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9755"},"statements":[{"statement_type":"Markdown","content":"你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。\n\n森林的地图有 $n$ 片地块，其中 $1$ 号地块连接森林的入口。共有 $n-1$ 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。\n\n你的目标是：在每片地块上均种植一棵树木，并使得 $i$ 号地块上的树的高度生长到不低于 $a_i$ 米。\n\n你每天可以选择一个未种树且**与某个已种树的地块直接邻接**（**即通过单条道路相连**）的地块，种一棵高度为 $0$ 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 $1$ 天你只能在 $1$ 号空地种树。\n\n对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 $x$ 天，$i$ 号地块上的树会长高 $\\max(b_i + x \\times c_i, 1)$ 米。注意这里的 $x$ 是从整个任务的第一天，而非种下这棵树的第一天开始计算。\n\n你想知道：最少需要多少天能够完成你的任务？\n\n## Input\n\n输入的第一行包含一个正整数 $n$，表示森林的地块数量。\n\n接下来 $n$ 行：每行包含三个整数 $a_i, b_i, c_i$，分别描述一片地块，含义如题目描述中所述。\n\n接下来 $n-1$ 行：每行包含两个正整数 $u_i, v_i$，表示一条连接地块 $u_i$ 和 $v_i$ 的道路。\n\n## Output\n\n输出一行仅包含一个正整数，表示完成任务所需的最少天数。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n第 $1$ 天：在地块 $1$ 种树，地块 $1$ 的树木长高至 $2$ 米。\n\n第 $2$ 天：在地块 $3$ 种树，地块 $1, 3$ 的树木分别长高至 $5, 3$ 米。\n\n第 $3$ 天：在地块 $4$ 种树，地块 $1, 3, 4$ 的树木分别长高至 $9, 6, 4$ 米。\n\n第 $4$ 天：在地块 $2$ 种树，地块 $1, 2, 3, 4$ 的树木分别长高至 $14, 1, 9, 6$ 米。\n\n第 $5$ 天：地块 $1, 2, 3, 4$ 的树木分别长高至 $20, 2, 12, 7$ 米。\n\n**【样例 2】**\n\n见选手目录下的 `tree/tree2.in` 与 `tree/tree2.ans`。\n\n**【样例 3】**\n\n见选手目录下的 `tree/tree3.in` 与 `tree/tree3.ans`。\n\n**【样例 4】**\n\n见选手目录下的 `tree/tree4.in` 与 `tree/tree4.ans`。\n\n**【数据范围】**\n\n对于所有测试数据有：$1 \\le n \\le 10^5,1 \\le a_i \\le 10^{18}, 1 \\le b_i \\le 10^9,0 \\le |c_i| \\le 10^9, 1 \\le u_i, v_i \\le n$。保证存在方案能在 $10^9$ 天内完成任务。\n\n::cute-table{tuack}\n\n| 测试点编号 | $n \\leq$ | 特殊性质 |\n| :-: | :-: | :-: |\n| $1$ | $20$ | $\\text A$ |\n| $2\\sim4$ | ^ | 无 |\n| $5\\sim6$ | $500$ | $\\text A$ |\n| $7\\sim8$ | $10^5$ | ^ |\n| $9\\sim10$ | ^ | $\\text B$ |\n| $11\\sim13$ | ^ | $\\text C$ |\n| $14\\sim16$ | ^ | $\\text D$ |\n| $17\\sim20$ | ^ | 无 |\n\n特殊性质 $\\text A$：对于所有 $1 ≤ i ≤ n$，均有 $c_i = 0$；\n\n特殊性质 $\\text B$：对于所有 $1 ≤ i < n$，均有 $u_i = i,v_i = i + 1$；\n\n特殊性质 $\\text C$：与任何地块直接相连的道路均不超过 $2$ 条；\n\n特殊性质 $\\text D$：对于所有 $1 ≤ i < n$，均有 $u_i = 1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9755","tags":["贪心","二分","2023","O2优化","CSP-S 提高级"],"sample_group":[["4\n12 1 1\n2 4 -1\n10 3 0\n7 10 -2\n1 2\n1 3\n3 4","5\n"]],"created_at":"2026-03-03 11:09:25"}}