G: Restricted DFS

問題

N 頂点 N-1 辺からなる、自己ループや多重辺が存在しない無向木 G がある。頂点はそれぞれ 1 から N まで番号付けされており、辺もそれぞれ 1 から N-1 まで番号付けされており、i 番目の辺は u_i と v_i を結んでいる。また、i 番目の頂点には非負整数 A_i がそれぞれ割り当てられている。

この木に対して、根 r から以下の擬似コードにしたがって DFS (深さ優先探索) を行うことを考える。

// [input]
// G: dfs の対象となるグラフ
// A: それぞれの頂点に割り当てられた非負整数
// v: dfs を開始する頂点
// step: ステップ数を記録する整数

// [output]
// 以下のうちどちらかの二値
// - SUCCESS: dfs が途中で終了することなく、頂点 v まで戻ってくる
// - FAILURE: dfs が途中で終了する

function dfs(G, A, v, step)
    if (A[v] が 0 である) then
        return FAILURE

    A[v] ← A[v] - 1
    step ← step + 1
    v の子を頂点番号が小さい順にソート

    // c は頂点番号が小さい順に見られる
    for each (v の子 c) do
        if (dfs(G, A, c, step) が FAILURE である) then
            return FAILURE

        if (A[v] が 0 である) then
            return FAILURE

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

    return SUCCESS

つまり、与えられた G と A に対して、根 r について

dfs(G, A, r, 0)

を実行することを考える。

それぞれの頂点を根としたときの、この DFS のステップ数を求めよ。

入力形式

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

制約

出力形式

N 行出力せよ。i 行目には、頂点 i を根としたときのステップ数を出力せよ。

入力例1

3
1 2 3
1 2
1 3

出力例1

2
3
3

よって、答えはそれぞれ 2, 3, 3 となる。はじめに根から出発するときも A_i の値を減らすことに注意せよ。

入力例2

3
1 2 3
1 2
2 3

出力例2

4
4
5