DMOPC '20 Contest 6 P4 - Land of the Carrot Trees II

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

A hungry rabbit is wandering on a tree with N nodes, numbered 1, 2, \dots, N when they notice that the i-th node has a carrot with flavour F_i. The rabbit then decides to ask himself Q times: "If the tree were rooted at node u_j, how many subtrees would have at least k_j distinct flavours of carrots?" Having overheard this mumbling, you decide to write a program to answer his queries.

Constraints

1 \le N, Q \le 5 \times 10^5

1 \le F_i, u_j, k_j \le N

The edges form a tree.

Subtask 1 [20%]

1 \le N, Q \le 2 \times 10^3

Subtask 2 [50%]

k_x = k_y for all pairs (x, y).

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains 2 space-separated integers, N and Q.

The second line of input contains N space-separated integers, F_1, F_2, \dots, F_N.

The next N-1 lines contain 2 space-separated integers each, a_i, b_i, indicating there is an edge between a_i and b_i.

The next Q lines contain 2 space-separated integers each, u_j, k_j.

Output Specification

Output Q lines, where the j-th line contains the answer to the j-th query.

Sample Input

8 4
2 1 2 1 1 3 3 2
1 2
6 3
6 7
4 2
2 5
3 1
8 6
1 2
3 1
6 4
5 2

Sample Output

3
8
0
5

Explanation

The trees above are labeled with colours representing the flavours of the carrots.

For the first query, the tree is rooted at node 1, and we see that the subtrees rooted at nodes 1, 3, 6 have at least 2 distinct flavours of carrots.

For the second query, all subtrees have at least 1 distinct flavour of carrots.

For the third query, none of the subtrees have at least 4 distinct flavour of carrots.

For the fourth query, the tree is rooted at node 5, and we see that the subtrees rooted at nodes 1, 2, 3, 5, 6 have at least 2 distinct flavours of carrots.


Comments

There are no comments at the moment.