Problem Description

There is a tree with $n$ nodes, each node having a weight $v_i$, rooted at 1, with nodes numbered from 1 to $n$.

We want to select some nodes, subject to the following conditions:

1. A node cannot be selected if its parent node is not selected.
2. The set of selected nodes must not contain duplicate weights.
3. For each selected node, the weights of all selected nodes in its subtree must form an arithmetic sequence with a common difference of 1.

You need to output the number of valid schemes that satisfy the above conditions.

Note: A scheme refers to a set of selected nodes with distinct combinations.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $v_i$.

The following $n-1$ lines each contain two integers $a_i$ and $b_i$, describing an edge in the tree where $a_i$ is the parent and $b_i$ is the child.

Output Format

Output a single integer, the number of valid schemes that satisfy the above conditions.

Sample Input and Output

Sample Input #1

4
2 1 3 4
1 2
1 3
3 4

Sample Output #1

6

Sample Input #2

4
3 4 5 6
1 2
1 3
2 4

Sample Output #2

3

Sample Input #3

6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6

Sample Output #3

10

Notes

Sample Explanation

Sample 1 Explanation

The following are the six valid sets of node weights:

$\{2\},\{2,3\},\{2,3,4\},\{1,2,3,4\},\{1,2\},\{1,2,3\}$.

Sample 2 Explanation

The following are the three valid sets of node weights:

$\{3\},\{3,4\},\{3,4,5\}$.

Note that the node with weight $6$ cannot be selected because the subtree $\{4,6\}$ formed with its parent does not meet the condition.

Data Range and Constraints

• For $50\%$ of the test cases, $n \le 100$.
• For $100\%$ of the test cases, $1 \le n \le 10^4$, $1 \le v_i \le 100$, $1 \le a_i, b_i \le n$.

Notes

This problem is worth $160$ points.

This problem is translated from the Croatian Open Competition in Informatics 2015/2016 Contest #1 T6 UZASTOPNI.

见题面 Input 部分

见题面 Output 部分