Frequent color - MarisaOJ: Marisa Online Judge

Given a tree of

n

$n$ vertices rooted at

1

$1$ , vertex

i

$i$ has color

A_{i}

$A_i$ . Given

q

$q$ queries, each of the form

(u, x)

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

x

$x$ times in the subtree rooted at

u

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

n, q

$n, q$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

n - 1

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

u, v

$u, v$ , there is an edge between

u

$u$ and

v

$v$ . - The next

q

$q$ lines, each line contains two integers

u, x

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

1 \leq n, q \leq 10^{5}

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

1 \leq A_{i} \leq 10^{5}

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

1 \leq u, v, x \leq n

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

431222122324121123

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

Output:

121

$1 2 1$

Topic

Tree

Data structure

DSU

Rating

1800

Solution (0)

Solution