trees.cpp

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000000007
#define ll long long
#define ul unsigned long

const int max_size = 1e6+3;
vector<ll> adj[max_size];
map<ll, ll> beauty;



void dfs(ll node, ll& node_gcd, ll& sum, map<ll, ll> &vis) {
    vis[node] = 1;
    for(ll i = 0 ; i < adj[node].size(); i++){
            if(vis[adj[node][i]]) continue;

            ll add = __gcd( (node_gcd%MAX), (beauty[adj[node][i]]%MAX)   );
            sum+= (add%MAX);
            sum%=MAX;
            dfs(adj[node][i], add, sum, vis);
    }
}



int main() {

ll n;
cin>>n;

ll sum=0;
for(ll i = 0 ; i < n ; i++){
    ll t; cin>>t;
    beauty[i+1] = t;
    sum+=t;
}

ll u,v;
for(ll i = 0 ; i < n-1 ; i++) {
    cin>>u>>v;
    adj[u].push_back(v);
    //adj[v].push_back(u);
}

// now we need to traverse over all possible

for(ll i = 0 ; i < n ; i++){
    map<ll, ll> vis;
    ll sum2 = (adj[i+1].size() > 0)?beauty[i+1]: -1;
    if(sum2 != -1)
    dfs(i+1, sum2, sum, vis);
}

cout<<sum<<endl;




return 0;
}