#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int lcm(long long int a, long long int b) {
  return a * b / gcd(a, b);
}
long long int fexp(long long int a, long long int b) {
  long long int ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % 1000000007;
    b /= 2;
    a = a * a % 1000000007;
  }
  return ans;
}
long long int inverse(long long int a, long long int p) {
  return fexp(a, p - 2);
}
void ingraph(vector<vector<long long int> >& graph, long long int m) {
  long long int x, y;
  for (long long int i = 0; i < m; i++) {
    cin >> x >> y;
    x--, y--;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
}
long long int modify(long long int n) {
  long long int res = n;
  res %= 1000000007;
  res += 1000000007;
  res %= 1000000007;
  return res;
}
vector<long long int> sum(1000001);
vector<long long int> dist(1000001);
long long int dp[1000001];
vector<long long int> vec(1000001);
bool visited[1000001] = {0};
void dfs(vector<vector<long long int> >& graph, long long int v,
         long long int p) {
  visited[v] = 1;
  if (v != 0)
    dist[v] = dist[p] + 1;
  else
    dist[v] = 0;
  dp[0] += dist[v] * vec[v];
  sum[v] += vec[v];
  for (long long int u : graph[v]) {
    if (!visited[u]) {
      dfs(graph, u, v);
      sum[v] += sum[u];
    }
  }
}
void det(vector<vector<long long int> >& graph, long long int v,
         long long int p) {
  visited[v] = 1;
  if (v != 0) {
    dp[v] = dp[p] + sum[0] - 2 * sum[v];
  }
  for (long long int u : graph[v]) {
    if (!visited[u]) {
      det(graph, u, v);
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int t;
  t = 1;
  while (t--) {
    long long int n;
    cin >> n;
    for (long long int i = 0; i < n; i++) cin >> vec[i];
    vector<vector<long long int> > graph(n);
    ingraph(graph, n - 1);
    dfs(graph, 0, -1);
    for (long long int i = 0; i < n; i++) visited[i] = 0;
    det(graph, 0, -1);
    long long int mx = 0;
    for (long long int i = 0; i < n; i++) mx = max(dp[i], mx);
    cout << mx;
  }
}

### Prompt

Please formulate a CPP solution to the following problem:

You are given a tree consisting exactly of n vertices. Tree is a connected undirected graph with n-1 edges. Each vertex v of this tree has a value a_v assigned to it.

Let dist(x, y) be the distance between the vertices x and y. The distance between the vertices is the number of edges on the simple path between them.

Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be v. Then the cost of the tree is ∑_{i = 1}^{n} dist(i, v) ⋅ a_i.

Your task is to calculate the maximum possible cost of the tree if you can choose v arbitrarily.

Input

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

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^5), where a_i is the value of the vertex i.

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 one integer — the maximum possible cost of the tree if you can choose any vertex as v.

Examples

Input


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


Output


121


Input


1
1337


Output


0

Note

Picture corresponding to the first example: <image>

You can choose the vertex 3 as a root, then the answer will be 2 ⋅ 9 + 1 ⋅ 4 + 0 ⋅ 1 + 3 ⋅ 7 + 3 ⋅ 10 + 4 ⋅ 1 + 4 ⋅ 6 + 4 ⋅ 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121.

In the second example tree consists only of one vertex so the answer is always 0.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int lcm(long long int a, long long int b) {
  return a * b / gcd(a, b);
}
long long int fexp(long long int a, long long int b) {
  long long int ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % 1000000007;
    b /= 2;
    a = a * a % 1000000007;
  }
  return ans;
}
long long int inverse(long long int a, long long int p) {
  return fexp(a, p - 2);
}
void ingraph(vector<vector<long long int> >& graph, long long int m) {
  long long int x, y;
  for (long long int i = 0; i < m; i++) {
    cin >> x >> y;
    x--, y--;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
}
long long int modify(long long int n) {
  long long int res = n;
  res %= 1000000007;
  res += 1000000007;
  res %= 1000000007;
  return res;
}
vector<long long int> sum(1000001);
vector<long long int> dist(1000001);
long long int dp[1000001];
vector<long long int> vec(1000001);
bool visited[1000001] = {0};
void dfs(vector<vector<long long int> >& graph, long long int v,
         long long int p) {
  visited[v] = 1;
  if (v != 0)
    dist[v] = dist[p] + 1;
  else
    dist[v] = 0;
  dp[0] += dist[v] * vec[v];
  sum[v] += vec[v];
  for (long long int u : graph[v]) {
    if (!visited[u]) {
      dfs(graph, u, v);
      sum[v] += sum[u];
    }
  }
}
void det(vector<vector<long long int> >& graph, long long int v,
         long long int p) {
  visited[v] = 1;
  if (v != 0) {
    dp[v] = dp[p] + sum[0] - 2 * sum[v];
  }
  for (long long int u : graph[v]) {
    if (!visited[u]) {
      det(graph, u, v);
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int t;
  t = 1;
  while (t--) {
    long long int n;
    cin >> n;
    for (long long int i = 0; i < n; i++) cin >> vec[i];
    vector<vector<long long int> > graph(n);
    ingraph(graph, n - 1);
    dfs(graph, 0, -1);
    for (long long int i = 0; i < n; i++) visited[i] = 0;
    det(graph, 0, -1);
    long long int mx = 0;
    for (long long int i = 0; i < n; i++) mx = max(dp[i], mx);
    cout << mx;
  }
}

```