cf202-div 1-B - Apple Tree：搜索，数论，树的遍历

浏览数：21 / 时间：2015年06月11日

You are given a rooted tree with n vertices. In each leaf vertex there‘s a single integer — the number of apples in this vertex.

The weight of a subtree is the sum of all numbers in this subtree leaves. For instance, the weight of a subtree that corresponds to some leaf is the number written in the leaf.

A tree is balanced if for every vertex v of the tree all its subtrees, corresponding to the children of vertex v, are of equal weight.

Count the minimum number of apples that you need to remove from the tree (specifically, from some of its leaves) in order to make the tree balanced. Notice that you can always achieve the goal by just removing all apples.

Input

The first line contains integer n (2 ≤ n ≤ 10⁵), showing the number of vertices in the tree. The next line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁸), a_i is the number of apples in the vertex number i. The number of apples in non-leaf vertices is guaranteed to be zero.

Then follow n - 1 lines, describing the tree edges. Each line contains a pair of integers x_i, y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i) — the vertices connected by an edge.

The vertices are indexed from 1 to n. Vertex 1 is the root.

Output

Print a single integer — the minimum number of apples to remove in order to make the tree balanced.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the sin, cout streams cin, cout or the %I64d specifier.

Sample test(s)

Input

6
0 0 12 13 5 6
1 2
1 3
1 4
2 5
2 6

Output


题目大意：有一棵有根树，每个叶子节点上面有一定数量的苹果（非叶子节点上没有苹果），现在要使每一个节点它的各个子树上的苹果总数都相等，问至少需要拿走多少个苹果。

这题跟去年校内PK赛的一道暴力题很像，不过那题是一棵二叉树，范围又比较小，所以直接暴力枚举某叶子节点的值，再一层层的往上考虑就可以了。

而这题不一定是二叉树，而且范围比较大，这时我们可以假设整棵树的苹果总数为x，我们假设根节点有n棵子树，那么分给每棵子树的苹果数为1/n*x，并且x一定是n的倍数（刚开始就是因为没考虑到这种情况WA了几发-_-|||）。

利用递归，将子树的苹果平均分给子树的子树。。。

一直到叶子节点，此时我们可以知道，该叶子节点分到的苹果为x的几分之一（设为k），因此x为k的倍数，并且x/k不大于该叶子的原来的苹果数，根据这个，我们可以得到一个最小的x，最后再求一个不大于x的所有k的公倍数，得解。

另外，为了避免倍数累乘的时候溢出，当发现k>x时，易知只能将所有的苹果都移掉，直接输出即可。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <vector>
 5 using namespace std;
 6 #define MAXN 100010
 7 typedef long long ll;
 8 int n;
 9 int num[MAXN];
10 vector<int> G[MAXN];
11 ll x,sum=0,lcm=1;
12 ll gcd(ll a,ll b)
13 {
14     return b==0 ? a : gcd(b, a%b);
15 }
16 
17 void dfs(int cur=1, ll div=1LL, int fa=-1)
18 {
19     if(div>x)
20     {
21         cout<<sum;
22         exit(0);
23         return;
24     }
25     if(num[cur] || G[cur].size()<=1 && cur!=1) // 是叶子节点
26     {
27         x=min(x, num[cur]*div);
28         lcm=div*lcm/gcd(lcm,div);
29         return;
30     }
31     for(int i=0; i<G[cur].size(); i++)
32     {
33         if(G[cur][i]!=fa)
34             dfs(G[cur][i], div*(ll)(G[cur].size()-1*(cur!=1)),cur);
35     }
36 }
37 int main()
38 {
39     //freopen("in.txt","r", stdin);
40 
41     cin>>n;
42     for(int i=1; i<=n; i++)
43     {
44         scanf("%d", &num[i]);
45         sum+=(ll)num[i];
46     }
47     x=sum;
48     for(int i=1; i<=n-1; i++)
49     {
50         int u,v;
51         scanf("%d %d", &u, &v);
52         G[u].push_back(v);
53         G[v].push_back(u);
54     }
55     dfs();
56     cout<<sum-x+x%lcm;
57 
58     return 0;
59 }