#include <bits/stdc++.h>   using namespace std;   const int M = 100000 + 10;   int leaf[M];   vector<int> adj[M];   int childnum[M];   void dfs(int cur, int par) {     for (int i = 0; i < adj[cur].size(); i++) {       int nxt = adj[cur][i];       if (nxt != par) {         childnum[cur]++;         dfs(nxt, cur);       }     }   }   bool ok = true;   long long int coef[M];   long long int thres = 1e16 + 10;   void dfs1(int cur, int par) {     coef[cur] = childnum[par] * coef[par];     if (coef[cur] > thres) {       ok = false;       return;     }     for (int i = 0; i < adj[cur].size(); i++) {       int nxt = adj[cur][i];       if (nxt != par) {         dfs1(nxt, cur);       }     }   }   vector<int> leafnode;   long long int gcd(long long int x, long long int y) {     return y == 0 ? x : gcd(y, x % y);   }   int main() {     int n;     cin >> n;     long long int s = 0;     for (int i = 1; i <= n; i++) {       cin >> leaf[i];       s = s + leaf[i];     }     for (int i = 0; i < n - 1; i++) {       int u, v;       cin >> u >> v;       adj[u].push_back(v);       adj[v].push_back(u);     }     for (int i = 2; i <= n; i++) {       if (adj[i].size() == 1) {         leafnode.push_back(i);       }     }     dfs(1, 0);     coef[0] = 1;     childnum[0] = 1;     dfs1(1, 0);     long long int minv = -1;     for (int i = 0; i < leafnode.size(); i++) {       int curleaf = leafnode[i];       long long int x = leaf[curleaf];       long long int k = coef[curleaf];       long long int v = k * x;       if (minv == -1) {         minv = v;       } else {         minv = min(minv, v);       }     }     if (!ok) {       cout << s << endl;     } else {       long long int lcm = 1;       for (int i = 0; i < leafnode.size(); i++) {         int curleaf = leafnode[i];         long long int k = coef[curleaf];         long long int d = gcd(lcm, k);         lcm = lcm * k / d;         if (lcm > minv) {           ok = false;           break;         }       }       if (!ok) {         cout << s << endl;       } else {         lcm = minv / lcm * lcm;         long long int ans = 0;         for (int i = 0; i < leafnode.size(); i++) {           int curleaf = leafnode[i];           long long int k = coef[curleaf];           long long int x = lcm / k;           long long int val = leaf[curleaf] - x;           ans = ans + val;         }         cout << ans << endl;       }     }     return 0;   }   