#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define MAX 200200
#define inf 1000000000
#define pb push_back

struct node
{
    ll fi;
    ll se;

    node(int _fi = -inf, int _se = -inf)
    {
        fi = _fi;
        se = _se;
    }

    void add(const node& other)
    {
        if(other.fi > this->fi){
            this->se = this->fi;
            this->fi = other.fi;
        }else if(other.fi > this->se){
            this->se = other.fi;
        }
    }
};

int n;
vector<int> adj[MAX];
bool ok[MAX];
int w[MAX], ans[MAX];
node f[MAX];

void nhap()
{
    cin >> n;
    for(int i = 1; i<=n; i++) cin >> w[i];
    for(int i = 1; i<=n-1; i++){
        int a,b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    memset(ok,true,sizeof(ok));
}

void pre_compute()
{
    ok[1] = ok[0] = false;
    for(int i = 2; i*i <=n; i++){
        if(ok[i]){
            for(int j = i*i; j<=n; j+= i) ok[j] = false;
        }
    }
}

void dfs(int v, int par)
{
    f[v].se = -inf;
    f[v].fi = (ok[v])? w[v] : -inf;
    for(int u : adj[v]){
        if(u == par) continue;
        dfs(u,v);
        if(f[u].fi != -inf){
//            f[v].add(f[u]);
            f[v].add(node(f[u].fi + w[v], f[u].se + w[v]));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    nhap();
    pre_compute();
    dfs(1,-1);
    ll res = -inf;
    for(int i = 1; i<=n; i++) res = max(res, 1LL*(f[i].fi + f[i].se) - w[i]);
//    cout << res;
    ll mxtmp = -inf;
    for(int i = 1; i<=n; i++) if(ok[i]) mxtmp = max(mxtmp , 1LL*w[i]);
    cout << max(res, mxtmp);
//    for(int i = 1; i<=n; i++) cout << ans[i] << ' ';
//    cout << f[1].fi << ' ' << f[1].se;
    return 0;
}