Restricted DFS

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

inputFormat

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

// [

outputFormat

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

样例

3
1 2 3
1 2
1 3

2
3
3

</p>