种树（tree）XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【题目描述】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
森林的地图有n片地块，其中1号地块连接森林的入口。共有n−1条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
你的目标是：在每片地块上均种植一棵树木，并使得i号地块上的树的高度生长到不低于ai米。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相.连）的地块，种一棵高度为0米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第1天你只能在1号空地种树。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第x天，i号地块上的树会长高max(bi+x∗ci,1)XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
米。注意这里的x是从整个任务的第一天，而非种下这棵树的第一天开始计算。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
你想知道：最少需要多少天能够完成你的任务？XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入格式】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
从文件tree.in中读入数据。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入的第一行包含一个正整数n，表示森林的地块数量。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来n行：每行包含三个整数ai,bi,ci，分别描述一片地块，含义如题目描述中所述。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来n−1行：每行包含两个正整数ui,vi，表示一条连接地块ui和vi的道路。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出格式】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出到文件tree.out中。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出一行仅包含一个正整数，表示完成任务所需的最少天数。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例1输入】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4
12 1 1
2 4 ‐1
10 3 0
7 10 ‐2
1 2
1 3
3 4
【样例1输出】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 5
【样例1解释】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第1天：在地块1种树，地块1的树木长高至2米。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第2天：在地块3种树，地块1,3的树木分别长高至5,3米。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第3天：在地块4种树，地块1,3,4的树木分别长高至9,6,4米。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第4天：在地块2种树，地块1,2,3,4的树木分别长高至14,1,9,6米。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第5天：地块1,2,3,4的树木分别长高至20,2,12,7米。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例2】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
见选手目录下的tree/tree2.in与tree/tree2.ans。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例3】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
见选手目录下的tree/tree3.in与tree/tree3.ans。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例4】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
见选手目录下的tree/tree4.in与tree/tree4.ans。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【数据范围】XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于所有测试数据有：1≤n≤105，1≤ai≤1018,1≤bi≤109，0≤|ci|≤109，1≤ui,vi≤n。保证存在方案能在109天内完成任务XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
特殊性质A：对于所有1≤i≤n，均有ci=0；XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
特殊性质B：对于所有1≤i<n，均有ui=i，vi=i+1；XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
特殊性质C：与任何地块直接相连的道路均不超过2条；XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
特殊性质D：对于所有1≤i<n，均有ui=1。XHn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
