P3023 [USACO11OPEN] Soldering G

奶牛们已经学会了基本的焊接方法，她们会把某条电线的一个端点焊接到另一条电线的中间某个位置，但她们没有学会如何把两条电线的端点直接焊接起来，也没有学会怎么把电线剪断。注意一条电线的同一个位置可以焊接多条电线。 奶牛们决定用电线焊接出一张联通图。该图由 $N$ $(1\le N\le 50,000)$ 个点，$N-1$ 条长度为 $1$ 的边组成。每条边可以由一对整数 $A$ 和 $B$ $(1 \leq A \leq N; 1 \leq B \leq N; A \neq B)$ 描述，表示这条边连接了点 $A$ 和点 $B$。 焊接所用的电线要从当地的商店里买。越长的电线越贵，一条长度为 $L$ 的电线售价为 $L^2$。 给定奶牛准备焊接的图，请告诉奶牛怎么焊接才能最节约费用。

第 $1$ 行：一个整数 $N$。 第 $2 \sim N$ 行：两个以空格分隔的整数 $A$ 和 $B$，描述一条边。

第 $1$ 行：一个整数，将树焊接在一起的成本。 **请注意，此数字可能并不总是适合32位整数。**

由于整个图中的所有节点都连接到节点 $1$，我们只需要购买一根长度为 $2$ 的电线和三根长度为 $1$ 的电线，总成本为 $2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 = 7$。 对于至少 $50\%$ 的测试数据，有 $N \leq 2,000$。