Problem: You are given a tree consisting of n vertices. A tree is a connected undirected graph with n-1 edges. Each vertex v of this tree has a color assigned to it (a_v = 1 if the vertex v is white and 0 if the vertex v is black).

You have to solve the following problem for each vertex v: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex v? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains cnt_w white vertices and cnt_b black vertices, you have to maximize cnt_w - cnt_b.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

The second line of the input contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 1), where a_i is the color of the i-th vertex.

Each of the next n-1 lines describes an edge of the tree. Edge i is denoted by two integers u_i and v_i, the labels of vertices it connects (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i).

It is guaranteed that the given edges form a tree.

Output

Print n integers res_1, res_2, ..., res_n, where res_i is the maximum possible difference between the number of white and black vertices in some subtree that contains the vertex i.

Examples

Input


9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9


Output


2 2 2 2 2 1 1 0 2 


Input


4
0 0 1 0
1 2
1 3
1 4


Output


0 -1 1 -1 

Note

The first example is shown below:

<image>

The black vertices have bold borders.

In the second example, the best subtree for vertices 2, 3 and 4 are vertices 2, 3 and 4 correspondingly. And the best subtree for the vertex 1 is the subtree consisting of vertices 1 and 3.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long P = 1e9 + 7;
long long mod(long long n) { return (n % P + P) % P; }
long long modM(long long n, long long m) { return ((n % P * m % P) + P) % P; }
long long modA(long long n, long long m) { return ((n % P + m % P) + P) % P; }
long long modS(long long n, long long m) { return ((n % P - m % P) + P) % P; }
bool isPrime(long long n) {
  if (n <= 1) return false;
  for (long long i = 2; i < n; i++)
    if (n % i == 0) return false;
  return true;
}
unsigned long long power(unsigned long long x, long long y, long long p) {
  unsigned long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y);
long long modInverse(long long b, long long m) {
  long long x, y;
  long long g = gcdExtended(b, m, &x, &y);
  if (g != 1) return -1;
  return (x % m + m) % m;
}
long long modDivide(long long a, long long b, long long m) {
  a = a % m;
  long long inv = modInverse(b, m);
  if (inv == -1)
    cout << "lala", exit(0);
  else
    return (inv * a) % m;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
vector<long long> fac;
void fact(long long n) {
  fac.resize(n + 1, 1);
  for (long long i = 1; i <= n; i++) {
    fac[i] = modM(fac[i - 1], i);
  }
}
unsigned long long nCrModPFermat(unsigned long long n, long long r,
                                 long long p) {
  if (r == 0) return 1;
  if (r > n) return 0;
  return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) %
         p;
}
void prv(vector<long long> &a, long long n) {
  long long i = 0;
  for (long long x : a) {
    i++;
    cout << x << " ";
    if (i == n) break;
  }
  cout << '\n';
}
long long check(vector<vector<long long>> &vp, string &a, string &b) {
  for (long long i = 0; i < min(a.size(), b.size()); i++) {
    if (a[i] != b[i]) {
      vp[a[i] - 'a'].push_back(b[i] - 'a');
      return 0;
    }
  }
  if (b.size() < a.size()) {
    return 1;
  }
  return 0;
}
void scc(vector<vector<long long>> &v, set<long long> &h, long long node) {
  h.insert(node);
  for (auto i : v[node]) {
    if (h.count(i) == 0) scc(v, h, i);
  }
}
bool fin(vector<long long> &v, long long k) {
  long long ans = 0;
  for (auto i : v) {
    if (i % k == 0) ans++;
    if (ans >= 2) return 1;
  }
  return false;
}
long long logab(long long a, long long b) { return log(a) / log(b); }
bool func(const pair<long long, pair<long long, long long>> &p1,
          const pair<long long, pair<long long, long long>> &p2) {
  return p1.first >= p2.first;
}
void bfs(vector<vector<long long>> &v, vector<long long> &distance) {
  distance[1] = 0;
  queue<long long> q;
  q.push(1);
  while (q.size()) {
    long long node = q.front();
    q.pop();
    for (auto i : v[node]) {
      if (distance[i] == -1) {
        distance[i] = distance[node] + 1;
        q.push(i);
      }
    }
  }
}
void dfs(vector<vector<long long>> &v, vector<bool> &vis, long long node) {
  vis[node] = 1;
  for (auto i : v[node]) {
    if (!vis[i]) {
      dfs(v, vis, i);
    }
  }
}
bool check(string &a, string &b) {
  long long n = b.size() / a.size();
  string ans = "";
  for (long long i = 0; i < n; i++) ans += a;
  return ans == b;
}
void printDistSum(vector<vector<long long>> &dp, vector<long long> &arr,
                  long long n) {
  long long sum = 0;
  for (long long i = 0; i < n; i++) sum += arr[i];
  for (long long i = 0; i <= n; i++) dp[i][0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= sum; j++) {
      if (j - arr[i - 1] >= 0)
        dp[i][j] = modA(dp[i - 1][j], dp[i - 1][j - arr[i - 1]]);
      else
        dp[i][j] = dp[i - 1][j];
    }
  }
}
void find_primes(long long n, vector<long long> &primes) {
  bool isprime[n + 1];
  for (long long i = 0; i <= n; i++) isprime[i] = 1;
  isprime[0] = 0;
  isprime[1] = 0;
  for (long long i = 2; i <= n; i++) {
    if (isprime[i]) {
      for (long long j = i * i; j <= n; j += i) {
        isprime[j] = 0;
      }
    }
  }
  for (long long i = 0; i <= n; i++) {
    if (isprime[i]) {
      primes.push_back(i);
    }
  }
  return;
}
void factorize(vector<long long> &sp, unordered_map<long long, long long> &v,
               long long x) {
  long long n = x;
  while (x != 1) {
    v[sp[x]]++;
    x = x / sp[x];
  }
}
void find_fact1(long long n, vector<long long> &primes,
                vector<unordered_map<long long, long long>> &primfact) {
  vector<long long> cur(n + 1);
  for (long long i = 0; i <= n; i++) {
    cur[i] = i;
  }
  for (auto x : primes) {
    for (long long i = x; i <= n; i += x) {
      long long cnt = 0;
      while (cur[i] % x == 0) {
        cur[i] /= x;
        cnt++;
      }
      primfact[i][x] = cnt;
    }
  }
  return;
}
void find_fact2(long long n, vector<long long> &primes, vector<long long> &sp) {
  for (long long i = 0; i <= n; i++) {
    sp[i] = i;
  }
  for (auto x : primes) {
    for (long long i = x * 2; i <= n; i += x) {
      sp[i] = min(sp[i], x);
    }
  }
  return;
}
map<long long, long long> primeFactors(long long n) {
  map<long long, long long> h;
  while (n % 2 == 0) {
    h[2]++;
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      h[i]++;
      n = n / i;
    }
  }
  if (n > 2) h[n]++;
  return h;
}
long long fo(long long n, long long x) {
  long long ans = 0;
  while (n % x == 0) {
    ans++;
    n = n / x;
  }
  return ans;
}
void func(vector<long long> &ans, long long n, long long i) {
  if (i == n) {
    ans.push_back(1);
    return;
  }
  for (long long j = i + 1; j <= n; j++) {
    ans.push_back(i);
    ans.push_back(j);
  }
  return;
}
void dfs(vector<long long> &g, vector<vector<long long>> &v, long long node,
         long long pnode) {
  g.push_back(node);
  for (auto i : v[node]) {
    if (pnode != i) dfs(g, v, i, node);
  }
}
bool isprime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long nextPrime(long long N) {
  if (N <= 1) return 2;
  long long prime = N;
  bool found = false;
  while (!found) {
    prime++;
    if (isprime(prime)) found = true;
  }
  return prime;
}
void dfs(vector<vector<long long>> &v, vector<long long> &dp,
         vector<long long> &col, long long node, long long pnode) {
  dp[node] = col[node];
  for (auto i : v[node]) {
    if (i != pnode) {
      dfs(v, dp, col, i, node);
      dp[node] += max(dp[i], (long long)0);
    }
  }
}
vector<long long> ans(2e5 + 1, -1);
void dfs1(vector<vector<long long>> &v, vector<long long> &dp, long long node,
          long long pnode) {
  ans[node] = dp[node];
  for (auto i : v[node]) {
    if (i == pnode) continue;
    dp[node] -= max((long long)0, dp[i]);
    dp[i] += max((long long)0, dp[node]);
    dfs1(v, dp, i, node);
    dp[i] -= max((long long)0, dp[node]);
    dp[node] += max((long long)0, dp[i]);
  }
}
void solve() {
  long long n;
  cin >> n;
  vector<vector<long long>> v(n + 1);
  vector<long long> col(n + 1);
  for (long long i = 1; i <= n; i++) {
    cin >> col[i];
    if (col[i] == 0) col[i] = -1;
  }
  for (long long i = 0; i < n - 1; i++) {
    long long l, r;
    cin >> l >> r;
    v[l].push_back(r);
    v[r].push_back(l);
  }
  vector<long long> dp(n + 1);
  dfs(v, dp, col, 1, -1);
  dfs1(v, dp, 1, -1);
  for (long long i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long tc;
  tc = 1;
  for (long long t = 1; t <= tc; t++) {
    solve();
  }
}