#P1137. 种树
-
ID: 1137
Type: Default
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> 种树
題目描述
你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。
森林的地图有 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 的道路。
輸出格式
输出一行仅包含一个正整数，表示完成任务所需的最少天数。
Samples
4
12 1 1
2 4 -1
10 3 0
7 10 -2
1 2
1 3
3 4
5
提示
说明/提示
【样例 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≤n≤105，1≤ai≤1018,1≤bi≤109，0≤∣ci∣≤109,1≤ui,vi≤n。保证存在方案能在 109 天内完成任务。
| 測試點編號 | n <= | 特殊性質 |
| 1 | 20 | A |
| 2~4 | 無 | |
| 5~6 | 500 | A |
| 7~8 | 105 | |
| 9~10 | B | |
| 11~13 | C | |
| 14~16 | D | |
| 17~20 | 無 |
特殊性质 A：对于所有 1≤i≤n，均有 ci=0；
特殊性质 B：对于所有 1≤i<n，均有 ui=i，vi=i+1；
特殊性质 C：与任何地块直接相连的道路均不超过 2 条；
特殊性质 D：对于所有 1≤i<n，均有 ui=1。
原始資料
- Zero1 題號：
b138 - Hydro 題號：
Z1138 - Locale：
zh_TW - Display：
open