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}

• 1 行目では、与えられるグラフの頂点数 N が与えられる。
• 2 行目は N 個の整数からなる。i 個目の整数 A_i は、i 番目の頂点に書かれている値を表す。
• 3 行目から N+1 行目までは、与えられるグラフの辺の情報が与えられる。u_i, v_i は、頂点 u_i と頂点 v_i を結ぶ無向辺がグラフ中に存在することを表す。

制約

• 1 \leq N \leq 3 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq u_i < v_i \leq N
• 与えられるグラフは木であることが保証される
• 入力は全て整数で与えられる

出力形式

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

入力例1

3
1 2 3
1 2
1 3

出力例1

2
3
3

• 1 番目の頂点を根としたとき
• 頂点 1 (A_1: 1 → 0) → 頂点 2 (A_2: 2 → 1) → 頂点 1 (A_1 が 0 であるため、頂点 1 に訪れることなく終了する)
• 2 番目の頂点を根としたとき
• 頂点 2 (A_2: 2 → 1) → 頂点 1 (A_1: 1 → 0) → 頂点 3 (A_3: 3 → 2) → 頂点 1 (A_1 が 0 であるため、頂点 1 に訪れることなく終了する)
• 3 番目の頂点を根としたとき
• 頂点 3 (A_3: 3 → 2) → 頂点 1 (A_1: 1 → 0) → 頂点 2 (A_2: 2 → 1) → 頂点 1 (A_1 が 0 であるため、頂点 1 に訪れることなく終了する)

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

入力例2

3
1 2 3
1 2
2 3

出力例2

4
4
5