Đỏ Xanh (Thi thử MTTN 2022)
Xem PDFđề 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.
Nế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,
thì ở 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ỹ.
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.
Dù đã 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ả 🙂
Mỗ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 🙂
Mộ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\).
Mộ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 đỏ.
Hạ viện khai mạc, các nghị viên ngân nga giai điệu quốc ca Mỹ.
Sau đó, một dự luật mới được đưa ra để thảo luận. chac cac ban khong biet filibuster la gi dau...
Hesll 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ề.
Input
- 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)\)
- 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.
- \(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.
Output
- In ra một số duy nhất là đáp án, chia lấy dư cho \(10^9+2277\).
Scoring
- Subtask #1 (\(40\%\) số điểm): \(n \le 20\)
- Subtask #2 (\(30\%\) số điểm): \(n \le 200\)
- Subtask #3 (\(30\%\) số điểm): \(n \le 2000\)
Example
Test 1
Input
5
1 1 0 0 0
1 2
1 3
1 4
1 5Output
6Note
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]\)
Bình luận
Hint: Cải tiến từ subtask 2, chỉ duyệt chiều thứ 2 (biến \(delta\)) chạy từ \(-siz[u]\) tới \(+siz[u]\) với \(siz[u]\) là số nút trong cây con gốc \(u\)
Anh Quý ơi, ?cho em hỏi độ phức tạp bài này nếu duyệt theo cách của anh là bao nhiêu vậy ạ?
Cỡ tầm \(O(n^2)\) vì bây giờ mỗi lần duyệt cạnh \((u,v)\) là giống như gộp cây gốc \(v\) vào cây gốc \(u\).
Anh ơi, nhưng nếu cây dạng đường thẳng thì độ phức tạp của nó cũng gần bằng O(n^3) rồi đúng ko anh nhỉ?
Cây đường thẳng cũng O(n^2) thôi em :v. Ví dụ 1->2->3->4->5 thì
Bình thường mình QHĐ trên cây cũng là gộp cây này vào cây kia đó. DFS(u), lúc đầu cây con gốc u có duy nhất một nút u thôi, xong gộp con v của u vào thì được cây con gốc u lớn hơn.