G: Restricted DFS

problem

There is an undirected tree G that consists of N vertices N-1 edges and has no self-loops or multiple edges. The vertices are each numbered from 1 to N, the edges are also numbered from 1 to N-1, and the i-th edge connects u_i and v_i. A non-negative integer A_i is assigned to the i-th vertex.

Consider performing DFS (depth-first search) on this tree from the root r according to the following pseudo code.


// [input]
// G: Graph for dfs
// A: Non-negative integer assigned to each vertex
// v: Vertex starting dfs
// step: Integer to record the number of steps

// [output]
// Binary of either of the following
// --SUCCESS: dfs returns to vertex v without terminating prematurely
// --FAILURE: dfs ends prematurely

function dfs (G, A, v, step)
if (A [v] is 0) then
return FAILURE

A [v] ← A [v] ―― 1
step ← step + 1
Sort the children of v in ascending order of vertex number

// c is seen in ascending order of vertex number
for each (child c of v) do
if (dfs (G, A, c, step) is FAILURE) then
return FAILURE

if (A [v] is 0) then
return FAILURE

A [v] ← A [v] ―― 1
step ← step + 1

return SUCCESS


That is, for a given G and A, for the root r


dfs (G, A, r, 0)

Think about doing.

Find the number of DFS steps with each vertex as the root.

Input format


N
A_1 ... A_N
u_1 v_1
...
u_ {N-1} v_ {N-1}


* In the first line, the number of vertices N of the given graph is given.
* The second line consists of N integers. The i-th integer A_i represents the value written at the i-th vertex.
* From the 3rd line to the N + 1th line, the information of the edge of the given graph is given. u_i and v_i indicate that there is an undirected edge connecting the vertex u_i and the vertex v_i in the graph.



Constraint

* 1 \ leq N \ leq 3 \ times 10 ^ 5
* 0 \ leq A_i \ leq 10 ^ 9
* 1 \ leq u_i <v_i \ leq N
* The graph given is guaranteed to be a tree
* All inputs are given as integers



Output format

Output N lines. On the i-line, output the number of steps when the vertex i is the root.

Input example 1


3
one two Three
1 2
13


Output example 1


2
3
3


* When rooted at the first vertex
* Vertex 1 (A_1: 1 → 0) → Vertex 2 (A_2: 2 → 1) → Vertex 1 (Because A_1 is 0, it ends without visiting vertex 1)
* When rooted at the second vertex
* Vertex 2 (A_2: 2 → 1) → Vertex 1 (A_1: 1 → 0) → Vertex 3 (A_3: 3 → 2) → Vertex 1 (Because A_1 is 0, it ends without visiting vertex 1)
* When rooted at the third vertex
* Vertex 3 (A_3: 3 → 2) → Vertex 1 (A_1: 1 → 0) → Vertex 2 (A_2: 2 → 1) → Vertex 1 (Because A_1 is 0, it ends without visiting vertex 1)



Therefore, the answers are 2, 3 and 3, respectively. Note that we also reduce the value of A_i when we start from the roots in the beginning.

Input example 2


3
one two Three
1 2
twenty three


Output example 2


Four
Four
Five






Example

Input

3
1 2 3
1 2
1 3


Output

2
3
3
  
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
vector<vector<int> > g;
vector<int> A;
vector<vector<int> > dp;
vector<vector<int> > fail;
vector<int> fi;
vector<int> se;
vector<int> fi_sum;
vector<int> se_sum;
vector<int> sum;
pair<int, int> dfs1(int a, int p) {

	dp[a].resize(g[a].size(), 0);
	fail[a].resize(g[a].size(), 0);
	int f = 0;
	int step = 0;
	int t = 1;
	if (t > A[a]) {
		f = 1;
	}
	if (f == 0) {
		step++;
	}
	for (int i = 0; i < g[a].size(); i++) {
		if (g[a][i] != p) {
			pair<int, int> p = dfs1(g[a][i], a);
			dp[a][i] = p.first;
			if (f == 0) {
				step += dp[a][i];
			}
			fail[a][i] = p.second;
			f |= p.second;
			t++;
			if (t > A[a]) {
				f = 1;
			}
			if (f == 0) {
				step++;
			}
		}
	}
	return make_pair(step, f);
}

void dfs2(int a, int p, int j) {
	int idx = -1;
	for (int i = 0; i < g[a].size(); i++) {
		if (g[a][i] == p) {
			idx = i;
		}
	}
	if (idx >= 0) {
		fail[a][idx] = 0;
		if (fi[p] == -1) {

			if (j < A[p]) {
				dp[a][idx] = sum[p] - dp[p][j];
				if (A[p] < (int)g[p].size()) {
					dp[a][idx] += dp[p][A[p]];
					/*if (fail[p][A[p]]) {
						fail[a][idx] = 1;
						dp[a][idx] += A[p] - 1;
					}
					else {
						dp[a][idx] += A[p];
					}*/
					dp[a][idx] += A[p];
					fail[a][idx] = 1;
				}
				else {
					dp[a][idx] += (int)g[p].size();
				}

			}
			else {
				dp[a][idx] = sum[p] + A[p];
				fail[a][idx] = 1;
			}
		}
		else {
			if (j < fi[p]) {
				dp[a][idx] = fi_sum[p] - dp[p][j];
				dp[a][idx] += fi[p];
				fail[a][idx] = 1;
			}
			else if (j == fi[p]) {
				if (se[p] == -1) {
					dp[a][idx] = sum[p] - dp[p][j];
					if (A[p] < (int)g[p].size()) {
						dp[a][idx] += dp[p][A[p]];
						/*if (fail[p][A[p]]) {
							fail[a][idx] = 1;
							dp[a][idx] += A[p] - 1;
						}
						else {
							dp[a][idx] += A[p];
						}*/
						dp[a][idx] += A[p];
						fail[a][idx] = 1;
					}
					else {
						dp[a][idx] += (int)g[p].size();
					}
				}
				else {
					dp[a][idx] = se_sum[p] - dp[p][j];
					dp[a][idx] += se[p];
					fail[a][idx] = 1;
				}
			}
			else {
				dp[a][idx] = fi_sum[p];
				dp[a][idx] += fi[p] + 1;
				fail[a][idx] = 1;
			}
		}
	}
	fi[a] = -1;
	se[a] = -1;
	sum[a] = 0;
	for (int i = 0; i < min(A[a], (int)g[a].size()); i++) {
		if (fail[a][i] == 1) {
			if (fi[a] == -1) {
				fi[a] = i;
				fi_sum[a] = sum[a] + dp[a][i];
			}
			else if (se[a] == -1) {
				se[a] = i;
				se_sum[a] = sum[a] + dp[a][i];
			}
		}
		sum[a] += dp[a][i];
	}



	for (int i = 0; i < g[a].size(); i++) {
		if (g[a][i] != p) {
			dfs2(g[a][i], a, i);
		}
	}
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	A.resize(N);
	dp.resize(N);
	fail.resize(N);
	g.resize(N);
	fi.resize(N);
	se.resize(N);
	fi_sum.resize(N);
	se_sum.resize(N);
	sum.resize(N);

	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	int a, b;
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b; a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 0; i < N; i++) {
		sort(g[i].begin(), g[i].end());
	}

	dfs1(0, -1);
	dfs2(0, -1, -1);

	for (int a = 0; a < N; a++) {
		int f = 0;
		int step = 0;
		int t = 1;
		if (t > A[a]) {
			f = 1;
		}
		if (f == 0) {
			step++;
		}
		for (int i = 0; i < g[a].size(); i++) {
			if (f == 0) {
				step += dp[a][i];
			}
			f |= fail[a][i];
			t++;
			if (t > A[a]) {
				f = 1;
			}
			if (f == 0) {
				step++;
			}
		}
		cout << step << endl;

	}
}
