**Problem statement:**

Given a tree with N nodes and N-1 edges. Each node has a value associated with it.

You have to remove maximum number of edges such that the value of each resulted connected component is same.

The value of a connected component is the sum of values of it's nodes.

**Note:** Answer always exists as you can always remove zero edges, so that the whole tree remains connected.

**Input Format:**

First line contains integer N (number of nodes)

Second line contains N integers, where ith integer is value of ith node.

Next N-1 lines contains 2 integers u, v denoting there is an edge between node u and v of tree.

**Constraints:**

1 <= N <= 10^5

1 <= a[i] <= 10^3

**Output:**

The maximum number of edges you can remove from the tree such that it holds the condition given in the problem.

**Example:**

**Input:**

5

3 2 1 1 1

1 2

1 3

2 4

2 5

**Output:**

1

**Solution:**

(Based on ideas from @nvdrag123 , @anarchaworld and @LC150H100M )

**Basic idea:**

- Find all factors of sum, sum will be at max 10^8, so any number <= 10^8 will have at max 100 factors
- For all factors, check how many components we can break our tree into
- Start from the smallest factor and get first valid factor which satisfies above condition (small factor => more components => more edges removed)
- To check valid division, recursively calculate number of components for each subtree by pre computing subtree sum as shown in code below