#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define readll(x) scanf("%I64d",&x)
#define mod 1000000007
#define eps 1e-6
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 300002;
int n,w[N],parent[N];
vvi g(N),adjL(N);
ll ans = -infll;
ll downP[N],downBestP[N],upP[N],upBestP[N];
ll downN[N],downBestN[N],upN[N],upBestN[N];

void buildGraph(int i, int p){
    parent[i] = p;
    for(int j : adjL[i]) if(j != p){
        g[i].pb(j);
        buildGraph(j,i);
    }
}

void dfs(int i, int p){
    downP[i] = downN[i] = downBestP[i] = downBestN[i] = w[i];

    for(int j : g[i]) if(j != p){
        dfs(j,i);
        if(downP[j] > 0) downP[i] += downP[j];
        if(downN[j] < 0) downN[i] += downN[j];
        downBestP[i] = max(downBestP[i], downBestP[j]);
        downBestN[i] = min(downBestN[i], downBestN[j]);
    }

    downBestP[i] = max(downBestP[i], downP[i]);
    downBestN[i] = min(downBestN[i], downN[i]);
}

void getUp(int i, int p){
    upP[p] = upN[p] = upBestP[p] = upBestN[p] = w[p];
    for(int j : g[p]) if(j != i){
        if(downP[j] > 0) upP[p] += downP[j];
        if(downN[j] < 0) upN[p] += downN[j];
        upBestP[p] = max(upBestP[p], downBestP[j]);
        upBestN[p] = min(upBestN[p], downBestN[j]);
    }
    //parent of p
    if(upP[parent[p]] > 0) upP[p] += upP[parent[p]];
    if(upN[parent[p]] < 0) upN[p] += upN[parent[p]];
    upBestP[p] = max(upBestP[p], upBestP[parent[p]]);
    upBestN[p] = min(upBestN[p], upBestN[parent[p]]);

    upBestP[p] = max(upBestP[p], upP[p]);
    upBestN[p] = min(upBestN[p], upN[p]);
}

void go(int i, int p){
    getUp(i,p);
    ans = max(ans, max(downBestP[i] * upBestP[p], downBestN[i] * upBestN[p]));
    for(int j : g[i]) if(j != p) go(j, i);
}

int main(){
    readi(n);
    lp(i,1,n) readi(w[i]);
    lp(i,1,n-1){
        int a,b;
        read2i(a,b);
        adjL[a].pb(b);
        adjL[b].pb(a);
    }

    buildGraph(1,0);
    dfs(1,0);
    for(int i : g[1]) go(i,1);
    cout <<ans;
}


//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//ios::sync_with_stdio(0);cin.tie(0);