One Junior - Repovive Starter Round 6 | Repovive

19D. One Junior

2000 pts2s256 MB

You are given a tree with $n$ vertices, numbered from $1$ to $n$ . Vertex $i$ has a label $a_i$ . The labels are not necessarily distinct.

Choose one vertex as the root of the tree. This determines the parent and children of every vertex.

A vertex is called unhappy if both of the following conditions hold:

it has at least one child;
the label of every child is strictly greater than its own label.

Find the minimum possible number of unhappy vertices, and the number of choices of the root for which this minimum is attained.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$1 \le u_i, v_i \le n$
The given edges form a tree

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array}

Output

minimum \quad count

Samples

Input

Explanation

If vertex $2$ or vertex $3$ is chosen as the root, every vertex with at least one child also has a child whose label is smaller than its own label. Therefore, there are no unhappy vertices for either of these two roots.

Output

0 2

Input

Explanation

Choosing vertex $2$ , $3$ , or $4$ as the root creates exactly one unhappy vertex. Choosing either endpoint as the root creates two unhappy vertices, so the minimum is $1$ and it is attained by three roots.

Output

1 3

Input

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

Explanation

For every choice of the root except vertex $5$ , there are no unhappy vertices. Notice that vertices $1$ and $2$ have equal labels, so neither label is strictly greater than the other.

Output

0 5

You are given a tree with $n$ vertices, numbered from $1$ to $n$ . Vertex $i$ has a label $a_i$ . The labels are not necessarily distinct.

Choose one vertex as the root of the tree. This determines the parent and children of every vertex.

A vertex is called unhappy if both of the following conditions hold:

it has at least one child;
the label of every child is strictly greater than its own label.

Find the minimum possible number of unhappy vertices, and the number of choices of the root for which this minimum is attained.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$1 \le u_i, v_i \le n$
The given edges form a tree

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array}

minimum \quad count

For every choice of the root except vertex $5$ , there are no unhappy vertices. Notice that vertices $1$ and $2$ have equal labels, so neither label is strictly greater than the other.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

19D. One Junior

Constraints

Input

Output

Samples

19D. One Junior

Constraints

Input

Output

Samples