#include <bits/stdc++.h>
using namespace std;
vector<int> vec[100010];
long long a[100010];
long long s;
int n;
long long dfs(int f, int u, long long val) {
  int sz = vec[u].size(), v;
  long long ret = 0, mv = ((long long)1e18), tmp;
  if (sz == 1 && vec[u][0] == f)
    return (a[u] = ((val) < (a[u]) ? (val) : (a[u])));
  if (u != 1)
    val = val / (sz - 1) * (sz - 1) / (sz - 1);
  else
    val = val / sz * sz / sz;
  for (int i = 0; i < sz; i++) {
    v = vec[u][i];
    if (v == f) continue;
    tmp = dfs(u, v, val);
    mv = ((mv) < (tmp) ? (mv) : (tmp));
  }
  while (true) {
    tmp = mv;
    for (int i = 0; i < sz; i++) {
      v = vec[u][i];
      if (v == f) continue;
      if (a[v] > tmp) tmp = ((dfs(u, v, mv)) < (tmp) ? (dfs(u, v, mv)) : (tmp));
    }
    if (tmp == mv)
      break;
    else
      mv = tmp;
  }
  for (int i = 0; i < sz; i++)
    if (vec[u][i] != f) ret += a[vec[u][i]];
  return a[u] = ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%I64d", a + i), s += a[i];
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  long long ret = dfs(0, 1, ((long long)1e18));
  cout << s - ret << endl;
  return 0;
}
