import sys

# 再帰上限の引き上げ
sys.setrecursionlimit(200000)

def solve():
    # 入力を一括で読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(input_data[i])
        
    adj = [[] for _ in range(N + 1)]
    idx = N + 1
    for _ in range(N - 1):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        idx += 2
        adj[u].append(v)
        adj[v].append(u)
        
    INF = 4 * 10**18
    
    # -----------------------------------------------------
    # Li Chao Tree (タイムスタンプ世代管理付き・非再帰)
    # -----------------------------------------------------
    size = 1
    while size <= N + 5:
        size *= 2
        
    lct_a = [0] * (2 * size)
    lct_b = [-INF] * (2 * size)
    lct_time = [0] * (2 * size)
    state = {'time': 1}
    
    def add_line(a, b):
        curr_time = state['time']
        idx = 1
        L = 0
        R = size - 1
        while True:
            # 世代が古いノードを上書き
            if lct_time[idx] != curr_time:
                lct_a[idx] = a
                lct_b[idx] = b
                lct_time[idx] = curr_time
                break
                
            mid = (L + R) >> 1
            a_idx = lct_a[idx]
            b_idx = lct_b[idx]
            
            v_mid = a_idx * mid + b_idx
            n_mid = a * mid + b
            
            v_L = a_idx * L + b_idx
            n_L = a * L + b
            
            # 中央の評価値が高いなら直線を入れ替え
            if n_mid > v_mid:
                lct_a[idx] = a
                lct_b[idx] = b
                a = a_idx
                b = b_idx
                
            if L == R:
                break
                
            if (n_L > v_L) != (n_mid > v_mid):
                idx = idx << 1
                R = mid
            else:
                idx = (idx << 1) | 1
                L = mid + 1

    def query_line(x):
        curr_time = state['time']
        idx = 1
        L = 0
        R = size - 1
        res = -INF
        while True:
            # 現在の世代と一致する場合のみ計算
            if lct_time[idx] == curr_time:
                val = lct_a[idx] * x + lct_b[idx]
                if val > res:
                    res = val
            else:
                break
                
            if L == R:
                break
            mid = (L + R) >> 1
            if x <= mid:
                idx = idx << 1
                R = mid
            else:
                idx = (idx << 1) | 1
                L = mid + 1
        return res

    # -----------------------------------------------------
    # 重心分解 関連の変数準備
    # -----------------------------------------------------
    used = [False] * (N + 1)
    M = [-INF] * (N + 1)
    for i in range(1, N + 1):
        M[i] = A[i]
        
    val = [-INF] * (N + 1)
    depth_c = [0] * (N + 1)
    parent_c = [0] * (N + 1)
    sum_c = [0] * (N + 1)
    U_c = [0] * (N + 1)
    
    # -----------------------------------------------------
    # 分割統治 (Divide and Conquer) によるパス最大化
    # -----------------------------------------------------
    def DC(l, r, subtrees, sub_lines, A_c):
        if l == r:
            return
        mid = (l + r) >> 1
        
        # 左から右へのマッチング
        state['time'] += 1
        for i in range(l, mid + 1):
            for d, u in sub_lines[i]:
                add_line(-d, u)
                
        for i in range(mid + 1, r + 1):
            for v in subtrees[i]:
                res = query_line(depth_c[v])
                if res != -INF:
                    E = res + U_c[v] - A_c
                    if E > val[v]: val[v] = E
                    
        # 右から左へのマッチング
        state['time'] += 1
        for i in range(mid + 1, r + 1):
            for d, u in sub_lines[i]:
                add_line(-d, u)
                
        for i in range(l, mid + 1):
            for v in subtrees[i]:
                res = query_line(depth_c[v])
                if res != -INF:
                    E = res + U_c[v] - A_c
                    if E > val[v]: val[v] = E
                    
        DC(l, mid, subtrees, sub_lines, A_c)
        DC(mid + 1, r, subtrees, sub_lines, A_c)

    # -----------------------------------------------------
    # 重心分解の本体
    # -----------------------------------------------------
    def decompose(start_node):
        # 1. 部分木のサイズを計算して重心を特定
        q = [start_node]
        order = []
        parent = {start_node: -1}
        head = 0
        while head < len(q):
            u = q[head]; head += 1
            order.append(u)
            for v in adj[u]:
                if not used[v] and v != parent[u]:
                    parent[v] = u
                    q.append(v)
                    
        sz = {u: 1 for u in order}
        for u in reversed(order):
            p = parent[u]
            if p != -1:
                sz[p] += sz[u]
                
        total = sz[start_node]
        c = start_node
        while True:
            nxt = -1
            for v in adj[c]:
                if not used[v] and v != parent[c] and sz[v] > total // 2:
                    nxt = v
                    break
            if nxt != -1:
                c = nxt
            else:
                break
                
        used[c] = True
        
        # 2. 重心を起点とした部分木の情報を集める
        subtrees = [[c]]
        A_c = A[c]
        depth_c[c] = 0
        U_c[c] = A[c]
        parent_c[c] = c
        
        for v in adj[c]:
            if not used[v]:
                sub = []
                sq = [v]
                head = 0
                depth_c[v] = 1
                parent_c[v] = c
                sum_c[v] = A[c] + A[v]
                U_c[v] = sum_c[v] - 1
                
                # BFSで部分木内の距離とスコアを計算
                while head < len(sq):
                    u = sq[head]; head += 1
                    sub.append(u)
                    for nxt_v in adj[u]:
                        if not used[nxt_v] and nxt_v != parent_c[u]:
                            parent_c[nxt_v] = u
                            depth_c[nxt_v] = depth_c[u] + 1
                            sum_c[nxt_v] = sum_c[u] + A[nxt_v]
                            d = depth_c[nxt_v]
                            U_c[nxt_v] = sum_c[nxt_v] - d * (d + 1) // 2
                            sq.append(nxt_v)
                subtrees.append(sub)
                
        K = len(subtrees)
        sub_lines = []
        
        # 不要な直線の追加を防ぐため、同じ深さからは最大スコアだけを抽出
        for i in range(K):
            max_u = {}
            for u in subtrees[i]:
                d = depth_c[u]
                u_val = U_c[u]
                if d not in max_u or u_val > max_u[d]:
                    max_u[d] = u_val
            sub_lines.append(list(max_u.items()))
            
        # 3. 分割統治と葉から根への伝播
        if K > 1:
            DC(0, K - 1, subtrees, sub_lines, A_c)
            
            # BFSの訪問順序を逆順に辿ることで「葉から根」に伝播
            for i in range(1, K):
                for v in reversed(subtrees[i]):
                    p = parent_c[v]
                    if p != c and val[v] > val[p]: 
                        val[p] = val[v]
                        
            # 全体の答え配列に反映させつつ一時配列をクリーンアップ
            for i in range(K):
                for v in subtrees[i]:
                    if val[v] > M[v]: M[v] = val[v]
                    val[v] = -INF
                    
        # 4. 次の重心へ再帰
        for v in adj[c]:
            if not used[v]:
                decompose(v)

    # 処理開始
    decompose(1)
    
    # 全頂点の中でスコア最小となるものを探索
    ans = min(M[1:])
    print(ans)

if __name__ == '__main__':
    solve()