DMOPC '22 Contest 2 P4 - Falling Leaves

View as PDF

Submit solution


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

Author:
Problem type

During the season of autumn, leaves change colours and fall to the ground. To celebrate the autumn spirit, you are given a tree with N nodes and K different colours, where each node has a colour a_i, and 1 \le a_i \le K. For each colour C from 1 to K, you must answer a query on the tree. The following process occurs: every second, a random leaf node is removed from the tree, falling to the ground. This process ends when colour C is completely removed from the tree, or there is only 1 node left. Out of every possible sequence of falling leaves, determine the number of sequences where colour C is completely removed from the tree in the shortest amount of time. Note that if the colour does not exist, or the colour cannot be removed, there are 0 sequences where it is removed.

Constraints

1 \le K \le N \le 3 \times 10^5

1 \le a_i \le K

1 \le u_i,v_i \le N

Subtask 1 [30%]

1 \le N \le 3 \times 10^3

Subtask 2 [70%]

No additional constraints.

Input Specification

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

The next line contains N space-separated integers, the ith of which is a_i.

The next N-1 lines contain 2 space-separated integers u_i and v_i, denoting an edge between nodes u_i and v_i.

Output Specification

Output K lines, where the C-th line contains the number of sequences where colour C is completely removed from the tree in the shortest amount of time. Since these numbers may be large, please output the answers modulo 10^9+7.

Sample Input

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

Sample Output

24
105
630
Creative Commons Attribution 3.0 Unported

Comments

There are no comments at the moment.