T576520 X

你有一棵拥有 $n(n \geq 3)$ 个节点，且每个节点都有权值的树。如果树上存在两条路径 $x,y$，**路径上点的个数皆大于 $1$** ，且它们**有且仅有**一个公共节点，则称其为一个 $X$。 设两条路径交点的权值，两条路径的权值和分别为 $t,a,b$，定义 $X$ 的 **值**，为: $$ f(X) = t^2 + (a+b)\times t + ab $$ 你的同桌想知道树上最大的 $f(X)$ 应该是多少，请帮帮她。

第一行包含两个整数 $n(n \leq 2\times 10^5)$ 表示树上节点的个数。 接下来 $n - 1$ 行，每行两个整数 $x,y$ 表示节点 $x ,y$ 之间存在边连接。 接下来一行 $n$ 个整数(**注意有负数**)，表示 $n$ 个节点的权值(权值值域为 $[-1000,1000]$)。

输出一个整数，表示树上最大的 $X$ 的值。

**样例1**，只有路径 (1$\sim$2) 以及路径 (1$\sim$3) 满足路径长度大于1且只有一个公共交点的条件，因此答案为 $10^2 +(0+30)\times 10 + 0\times 30 =400 $ **样例2**，路径 (1$\sim$4) 以及路径 (1$\sim$3) 的 $f(X)$ 是最大的，答案为 $10^2 + (10 + 0) \times 10 + 10 \times 0 =200$ 共 16 个测试点，其中： * 2 个测试点满足 $n \leq 35$ * 另有 2 个测试点满足为一条链 * 另有 2 个测试点满足点权都相等