思路：dp

给定一棵树，树上每个节点的丑陋值为节点深度乘节点丑陋值$a_i$，树的丑陋值为所有节点丑陋值的和。我们能够将一整棵子树裁剪下来，并给某一个节点当子树，求最小的树的丑陋值。

树的深度能够通过一次遍历得到结果，因此树的每个节点的丑陋值也能够在计算节点的深度时，通过递归计算出来。

为了让整棵树的丑陋值最小，一个很直观的想法就是，将裁剪出来的这棵子树嫁接到根节点，也就是1号节点下。

定义：$sum[i]$表示节点$i$及其子树的丑陋值的和(不乘深度)，$depth[i]$表示第$i$个节点的深度。

题目描述

米小游是一名远近闻名的魔法师。

这天他受邀来到了一个国家，来帮这个国家的国王解决一个问题。这个国家的国王年轻时曾有一颗非常美丽的树，但是国王却不小心惹怒了一个十分邪恶的黑魔法师，于是黑魔法师施法，让这棵树变得十分丑陋。现在，这棵树一共有$n$个节点，根节点为$1$号节点，其深度为$1$。每个节点都被黑魔法师随机施加了一个丑陋值，丑陋值越大，越影响这棵树的美观度，影响值为该节点的深度乘其丑陋值。

国王苦苦寻找了半辈子解决方案，让无数魔法师尝试过，但都没办法将树变回原样。长时间受黑魔法影响，这棵树再也无法变为原样了。终于，国王找到了米小游，希望米小游能尽可能地将树的丑陋值减少，并承诺，减少了多少丑陋值，就给米小游多少钱。

米小游看了看树，发现受黑魔法影响，只能裁剪树的一部分将其嫁接到另一个节点上。米小游想挣尽可能多的钱，因此他想知道能将树的丑陋值降到的最小值是多少？

注：只能裁剪一次。

输入描述

第一行输入一个整数 $n(1 \leq n \leq 10^5)$表示的大小

第二行输入$n$个整数$a(1 \leq a_i \leq 10^8)$表示每个节点的丑陋值

接下来$n-1$行，每行输入两个整数$u,u(1 \leq u,u \leq n)$，表示树上的边

输出描述

输出一个整数表示最小的丑陋值.

样例

输入

4
3 2 1 4
1 2
1 3
3 4

输出

17