Description

Here is a tree with $n$ nodes. Each node on the tree has a weight $v_i$. The tree is rooted at $1$, and the nodes are numbered from $1$ to $n$.

Now we want to select some nodes and satisfy the following conditions:

1. If a node’s parent is not selected, then this node cannot be selected.
2. Within the set of selected nodes, there cannot be duplicate weights.
3. For every selected node, the weights of all selected nodes in its subtree must be able to form an arithmetic progression with common difference $1$.

You only need to output the number of selection plans that satisfy the conditions above.

Note: a “plan” here means different sets of selected weights.

Input Format

The first line contains an integer $n$.

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

The next $n-1$ lines each contain two integers $a_i, b_i$. The $i$-th line describes an edge in the tree where $a_i$ is the parent and $b_i$ is the child.

Output Format

Only one line with one integer, representing the number of plans that satisfy the conditions above.

4
2 1 3 4
1 2
1 3
3 4 

6

4
3 4 5 6
1 2
1 3
2 4

3

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

10

Hint

Sample Explanation

Sample 1 Explanation

The following are the six possible sets of selected weights:

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

Sample 2 Explanation

The following are the three possible sets of selected weights:

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

Note that you cannot select the node with weight $6$, because the subtree $\{4,6\}$ formed by it and its parent does not meet the condition.

Constraints and Limits

• For $50\%$ of the testdata, it is guaranteed that $n \le 100$.
• For $100\%$ of the testdata, it is guaranteed that $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 in total.

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

Translated by ChatGPT 5