Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB

#2750. 删点(del)

统计

【题目描述】

给定一颗包含n个点的有根树,以1为根,每个点有三个参数 ai,bi,ci 你可以进行若干次如下操作:

·选择一个未删的点u,将它到它目前所在子树的根的路径上所有点删去,设路径上的边数为l

·花费代价为: au×l2+bu×l+cu

【输入格式】

从文件 del.in 中读入数据。

第一行,一个正整数n

接下来n-1行中,其中第i行两个正整数 ui,vi ,表示树上的一条边

接下来n行,其中三个整数 ai,bi,ci ,表示i点的三个参数

【输出格式】

输出到文件 del.out 中。

对于每组数据,输出一行,一个自然数,表示答案。

【样例输入1】

7
1 2
2 3
2 4
2 5
5 6
3 7
−2 −3 −1
−2 4 3
−1 −2 −3
−2 −1 −1
0 0 −5
−5 −2 0
−4 5 −5

【样例输出1】

-60

【数据范围】

对于前30%的数据,n20

对于另20%的数据,ui=vi1

对于所有数据,n5000|ai|,|bi|,|ci|109