【题目描述】

给定一颗包含n个点的有根树，以1为根，每个点有三个参数 $a_i,b_i,c_i$ 你可以进行若干次如下操作：

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

·花费代价为： $a_u\times l^2+b_u\times l+c_u$

【输入格式】

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

第一行，一个正整数n

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

接下来n行，其中三个整数 $a_i,b_i,c_i$ ，表示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\leq 20$

对于另20%的数据，$u_i=v_i-1$

对于所有数据，$n\leq 5000$，$|a_i|,|b_i|,|c_i|\leq 10^9$。