#include <bits/stdc++.h>

using LL = long long;

const int N = 1e3 + 7;

int n, m, a[N];
std::vector<int> e[N];
int lch[N], rch[N], d[N], sz[N];
LL val[N], b[N];

int merge(int x, int y) {
  if(!x || !y)
    return x + y;
  if(val[x] < val[y])
    std::swap(x, y);
  sz[x] += sz[y];
  rch[x] = merge(rch[x], y);
  if(d[rch[x]] > d[lch[x]])
    std::swap(lch[x], rch[x]);
  d[x] = d[rch[x]] + 1;
  return x;
}

int dfs(int x, int y) {
  int rt = 0;
  for(int v: e[x])
    if(v != y) {
      int t = dfs(v, x);
      rt = merge(rt, t);
      b[x] += b[v];
    }
  LL now = a[x];
  while(sz[x] >= 2 && now < val[rt]) {
    now -= val[rt];
    rt = merge(lch[rt], rch[rt]);
    now += val[rt];
    rt = merge(lch[rt], rch[rt]);
  }
  if(now >= val[rt]) {
    val[x] = now;
    sz[x] = d[x] = 1;
    rt = merge(rt, x);
    return rt;
  }
  assert(sz[rt] == 1);
  b[x] += now - val[rt];
  return 0;
}

int main() {

  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  for(int i = 1, x, y; i < n; ++i) {
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }

  val[0] = -1e18;
  int rt = dfs(1, 0);

  LL ans = (sz[rt] & 1 ? -b[1] : b[1]);
  for(int i = 1; rt; i = -i) {
    ans += i * val[rt];
    rt = merge(lch[rt], rch[rt]);
  }

  printf("%lld\n", ans);
  
  return 0; 

}