Frequent color - MarisaOJ: Marisa Online Judge

Given a tree of

$n$ vertices rooted at

$1$ , vertex

$i$ has color

$A_i$ . Given

$q$ queries, each of the form

$(u, x)$ , count the number of colors appear at least

$x$ times in the subtree rooted at

$u$ . ### Input - The first line contains two integers

$n, q$ . - The second line contains

$n$ integers

$A_i$ . - The next

$n - 1$ lines, each line contains two integers

$u, v$ , there is an edge between

$u$ and

$v$ . - The next

$q$ lines, each line contains two integers

$u, x$ , a query. ### Output - Print the answer for each query. ### Constraints -

$1 \le n,q\le 10^5$ . -

$1 \le A_i \le 10^5$ . -

$1 \le u, v,x \le n$ . ### Example Input:

$4 3 1 2 2 2 1 2 2 3 2 4 1 2 1 1 2 3$

Output:

$1 2 1$

Topic

Tree

Data structure

DSU

Rating

1800

Solution (0)

Solution