Color Balanced Subtrees

You are given a tree with n nodes numbered from \(1\) to \(n\) where node \(1\) is the root. Each node \(i\) has a color \(C_i\). A subtree (defined as a node along with all of its descendants) is called color balanced if for every color that appears in that subtree, the number of nodes having that color is the same.

For example, consider a subtree containing nodes of two distinct colors with frequencies \(a\) and \(b\) respectively. This subtree is balanced if \(a = b\). Note that a single node (which has only one color) is always color balanced.

Your task is to count how many subtrees in the given tree are color balanced.

The counts for each subtree are determined using the following idea: during a DFS from the root, for each node you aggregate the frequencies of colors in its subtree. Then, if all the frequencies in the aggregate are equal, you count that subtree as balanced.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(n\) representing the number of nodes in the tree.

The second line contains \(n\) integers \(C_1, C_2, \dots, C_n\) where \(C_i\) represents the color of the \(i^{th}\) node.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating that there is an edge between nodes \(u\) and \(v\). It is guaranteed that the tree is rooted at node \(1\).

outputFormat

Output a single integer representing the number of subtrees that are color balanced.

sample

3
1 2 1
1 2
1 3

2