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

View as PDF

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

Author:
Problem types

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.

for all pairs .

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.