{"code":"dhbbkiosks","name":"Trung tâm mua sắm (DHBB 2021)","description":"Một trung tâm mua sắm có $n$ kiốt (kiosk) đánh số từ $1$ tới $n$, kiốt thứ $i$ bán mặt hàng $c_i$\r\n. Siêu thị\r\ncó $n − 1$ con đường hai chiều đánh số từ $1$ tới $n − 1$, con đường thứ $i$ nối giữa kiốt $u_i$ và kiốt $v_i$\r\n.\r\nHệ thống các con đường đi đảm bảo sự đi lại giữa hai kiốt bất kỳ.\r\n\r\nTrong thời kỳ dịch bệnh, người ta muốn ngưng hoạt động một số kiốt để dễ dàng kiểm soát các\r\nhoạt động mua bán cũng như giao tiếp với khách hàng. Khi một kiốt bị ngừng hoạt động, tất cả\r\ncác con đường nối tới kiốt đó đều bị chặn để đảm bảo an ninh. Ngoài ra vì không muốn ảnh\r\nhưởng nhiều tới khách hàng, siêu thị muốn lập phương án sao cho các kiốt vẫn còn hoạt động\r\nphải thỏa mãn hai điều kiện sau:\r\n\r\n- Các kiốt còn hoạt động phải liên thông với nhau: Tức là giữa hai kiốt bất kỳ vẫn được mở\r\ncửa phải tồn tại đường đi (qua các con đường không bị chặn)\r\n- Tất cả các mặt hàng mang số hiệu từ $1$ tới $k$ (là những mặt hàng thiết yếu) đều phải có bán\r\nở ít nhất một kiốt còn hoạt động.\r\n\r\nHai phương án được gọi là khác nhau nếu có một kiốt bị ngưng hoạt động trong một phương án\r\nnhưng được phép hoạt động trong phương án còn lại.\r\nYêu cầu: Hãy cho biết có bao nhiêu phương án khác nhau thỏa mãn điều kiện nêu trên.\r\n\r\n<h4>Input</h4>\r\n\r\nVào từ file văn bản KIOSKS.INP\r\n- Dòng 1 chứa số nguyên dương $n \\le  10^4\r\n, k \\le  10$\r\n- Dòng 2 chứa n số nguyên dương $c_1, c_2, ... , c_n (\\forall i: c_i \\le  n)$\r\n- $n − 1$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $u_i\r\n, v_i$\r\n\r\n<h4>Output</h4>\r\n\r\n- Ghi ra file văn bản KIOSKS.OUT một số nguyên duy nhất là số dư trong phép chia: số\r\nphương án thỏa mãn điều kiện đề bài cho $1000000007 (10^9 + 7)$\r\n\r\n<h4>Scoring</h4>\r\n\r\n- Subtask $1$ ($30\\%$ số điểm): $k = 1$\r\n- Subtask $2$ ($30\\%$ số điểm): Mỗi kiốt có không quá 2 con đường nối tới nó.\r\n- Subtask $3$ ($40\\%$ số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 3\r\n        1 2 4 3\r\n        1 2\r\n        2 3\r\n        3 4\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ``` \r\n    \r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 2\r\n        1 2 2 2 3\r\n        1 2\r\n        1 3\r\n        1 4\r\n        2 5\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        11\r\n        ```","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}