CodeForces 348B Apple Tree

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 const LL INF = (1LL << 60);
 9 
10 const int maxn = 200000 + 10;
11 int n;
12 LL val[maxn];
13 vector<int> G[maxn];
14 
15 LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
16 LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
17 
18 LL L = INF, M = 1, sum;
19 
20 void dfs(int u, int fa, LL d)
21 {
22     M = lcm(M, d);
23     if(d > sum || d < 0) { printf("%I64d\n", sum); exit(0); }
24     if(u > 1 && G[u].size() == 1) L = min(L, val[u] * d);
25     for(int v : G[u]) if(v != fa)
26         dfs(v, u, d * (G[u].size() - (u == 1 ? 0 : 1)));
27 }
28 
29 int main()
30 {
31     scanf("%d", &n);
32     for(int i = 1; i <= n; i++) { scanf("%I64d", val + i); sum += val[i]; }
33     for(int i = 1; i < n; i++)
34     {
35         int u, v; scanf("%d%d", &u, &v);
36         G[u].push_back(v); G[v].push_back(u);
37     }
38 
39     dfs(1, 0, 1);
40     printf("%I64d\n", sum - L / M * M);
41 
42     return 0;
43 }