{"code":"kkkk","name":"Đỏ Xanh (Thi thử MTTN 2022)","description":"**đề bài mang tính chất không liên quan và không hề mô tả cách quốc hội Hoa Kỳ hoạt động**.\r\n\r\nNếu ở một vũ trụ nào đó, the delegate of Bảnh would like to raise an unmoderated caucus to play BlackJack in the UnitedNations,<br>\r\nthì ở thế giới song song năm 2077, Hesll(Hét-xồ) phải ngồi dự khán buổi họp quốc hội Mỹ.\r\n\r\n**Anh** ta đang ngồi **nhàn** rỗi nhâm **nhi** ly cà phê ở nơi họp của Hạ viện. Chỗ ngồi của các đại biểu lúc này không còn ngồi theo hình bán nguyệt, mà ngồi theo hình của một cái cây - cụ thể là một đồ thị đơn vô hướng không có chu trình, với mỗi dân biểu ngồi ở một đỉnh.<br>\r\nDù đã là năm 2077 nhưng cả Quốc hội đến lúc này vẫn không có nỗi một thành viên của đảng thứ ba. **Hảo** kết quả :) <br>\r\nMỗi dân biểu theo đảng Dân chủ (màu Xanh) hoặc đảng Cộng hòa (màu Đỏ). Hai ông này nhiều **ân** oán với nhau lắm :)\r\n\r\nMột nhóm nghị sỹ $S$ được gọi là ngồi gần nhau, nếu đường đi đơn giữa hai chỗ ngồi bất kỳ trong nhóm đều chỉ đi qua các chỗ ngồi khác cùng nằm trong $S$.<br>\r\nMột nhóm nghị sỹ được gọi là \"có thể thỏa hiệp\" nếu họ ngồi gần nhau và số thành viên bên xanh phải bằng số thành viên bên đỏ.\r\n\r\nHạ viện khai mạc, các nghị **viên** **ngân** nga giai điệu quốc ca Mỹ. <br>\r\nSau đó, một dự luật mới được đưa ra để thảo luận. chac cac ban khong biet filibuster la gi dau... <br>\r\nHesll hỏi ông **tiên** xem có bao nhiêu nhóm nghị sỹ có thể thỏa hiệp để vui vẻ, hạnh **phúc** ra về.\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên là $n$, biểu thị số lượng nghị sỹ trong Hạ viện $(n \\le 2000, n \\neq 435)$\r\n- Dòng tiếp theo gồm $n$ số: $c_1, c_2, \\dots, c_n$ biểu thị màu sắc của đảng phải của các nghị sĩ. $c_i=0$ nếu nghị sĩ thứ i thuộc Dân chủ, $c_i=1$ nếu là Cộng hòa.\r\n- $n - 1$ dòng cuối cùng, mỗi dòng chứa 2 số $u, v$ biểu thị 1 cạnh của sơ đồ chỗ ngồi.\r\n\r\n#### Output\r\n\r\n- In ra một số duy nhất là đáp án, chia lấy dư cho $10^9+2277$.\r\n\r\n#### Scoring\r\n\r\n- Subtask #1 ($40\\%$ số điểm): $n \\le 20$\r\n- Subtask #2 ($30\\%$ số điểm): $n \\le 200$\r\n- Subtask #3 ($30\\%$ số điểm): $n \\le 2000$\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5\r\n        1 1 0 0 0\r\n        1 2\r\n        1 3\r\n        1 4\r\n        1 5\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        6\r\n        ```\r\n    \r\n    ??? warning \"Note\"\r\n        \r\n        Các nhóm nghị sĩ sau thỏa mãn: $[1, 3], [1, 4], [1, 5], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5]$","points":100.0,"partial":false,"time_limit":2.0,"memory_limit":524188,"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}}