A hungry rabbit is wandering on a tree with nodes, numbered
when they notice that the
-th node has a carrot with flavour
. The rabbit then decides to ask himself
times: "If the tree were rooted at node
, how many subtrees would have at least
distinct flavours of carrots?" Having overheard this mumbling, you decide to write a program to answer his queries.
Constraints
The edges form a tree.
Subtask 1 [20%]
Subtask 2 [50%]
for all pairs
.
Subtask 3 [30%]
No additional constraints.
Input Specification
The first line contains space-separated integers,
and
.
The second line of input contains space-separated integers,
.
The next lines contain
space-separated integers each,
,
, indicating there is an edge between
and
.
The next lines contain
space-separated integers each,
,
.
Output Specification
Output lines, where the
-th line contains the answer to the
-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 , and we see that the subtrees rooted at nodes
have at least
distinct flavours of carrots.
For the second query, all subtrees have at least distinct flavour of carrots.
For the third query, none of the subtrees have at least distinct flavours of carrots.
For the fourth query, the tree is rooted at node , and we see that the subtrees rooted at nodes
have at least
distinct flavours of carrots.
Comments