【题目描述】
给定一颗包含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%的数据,n≤20
对于另20%的数据,ui=vi−1
对于所有数据,n≤5000,|ai|,|bi|,|ci|≤109。