LQDOJ Cup 2024 - Round #1

Với mỗi submission AC trong thời gian chính thức của contest LQDOJ Cup 2024 - Round #1, các bạn đã đóng góp 12.500 VNĐ vào quỹ ủng hộ đồng bào khắc phục sự cố cơn bão Yagi. Số tiền này sẽ được tổng hợp và chuyển tới Mặt trận Tổ quốc Việt Nam sau khi việc kiểm tra được hoàn tất.

Thành phố Hà Nội có thể được chia thành \(n\) khu vực, các khu vực được đánh số từ \(1\) đến \(n\), khu vực thứ \(i ~ (1 \leq i \leq n)\) có \(a_i\) người sinh sống.

Việc di chuyển giữa hai khu vực bất kì trong thành phố đều phải thông qua các con đường. Có tất cả \(m\) con đường, con đường thứ \(i ~ (1 \leq i \leq m)\) kết nối hai khu vực \(u_i\) và \(v_i\). Đảm bảo rằng mọi con đường đều kết nối hai khu vực khác nhau và không có hai con đường nào kết nối cùng một cặp khu vực. Từ một khu vực bất kì có thể đi đến tất cả các khu vực còn lại thông qua các con đường.

Siêu bão YAGI đã đi qua các tỉnh miền Bắc, gây ra rất nhiều thiệt hại cho người dân. Chưa kịp khắc phục hoàn toàn hậu quả của cơn bão thì bây giờ người dân lại nghe "tin dữ" về lũ sông Hồng.

Cục quản lý đê điều và phòng, chống thiên tai dự đoán rằng trong trường hợp xấu nhất, tất cả các khu vực của thành phố sẽ lần lượt bị ngập nhưng không có hai khu vực nào bị ngập cùng một lúc, do đó thứ tự bị ngập của các khu vực có thể được biểu diễn bởi một hoán vị \(p_1, p_2, \ldots, p_n ~ (1 \leq p_i \leq n)\) của các số nguyên từ \(1\) đến \(n\), trong đó \(p_i\) là số hiệu của khu vực bị ngập thứ \(i\).

Để dự đoán mức thiệt hại mà lũ sông Hồng gây ra cho thành phố Hà Nội, cục quyết định khảo sát các tình huống có thể xảy ra. Mỗi tình huống tương ứng với một hoán vị \(p_1, p_2, \ldots, p_n\) là thứ tự bị ngập lụt của các khu vực. Với mỗi tình huống \(p_1, p_2, \ldots, p_n\), mức thiệt hại của tình huống đó được tính như sau:

• Các khu vực lần lượt bị ngập, khu vực bị ngập thứ \(i\) có số hiệu là \(p_i\). Ta gọi mức ảnh hưởng của khu vực \(p_i\) trong tình huống này là tổng số người sinh sống trong các khu vực chưa bị ngập (tại thời điểm ngay sau khi khu vực \(p_i\) bị ngập) và được kết nối trực tiếp với \(p_i\).
• Mức thiệt hại của tình huống này là tổng các mức ảnh hưởng của tất cả \(n\) khu vực.

Yêu cầu: Hãy tính tổng mức thiệt hại của tất cả các tình huống có thể xảy ra.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, m\) \((2 \leq n \leq 2 \times {10}^5\), \(1 \leq m \leq \min(5 \times {10}^5, \frac{n(n-1)}{2}))\) lần lượt là là số khu vực và số con đường giữa các khu vực.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n ~ (1 \leq a_i \leq {10}^9)\).
• \(m\) dòng tiếp theo, dòng thứ \(i ~ (1 \leq i \leq m)\) gồm hai số nguyên dương \(u_i, v_i ~ (1 \leq u_i, v_i \leq n)\) thể hiện rằng con đường thứ \(i\) kết nối hai khu vực \(u_i\) và \(v_i\).

Output

• Một số nguyên duy nhất là tổng mức thiệt hại trong tất cả mọi tình huống, vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho \(({10}^9 + 7)\).

Scoring

• Subtask 1 (\(29\%\) số điểm): \(n \leq 10\).
• Subtask 2 (\(23\%\) số điểm): \(n \leq 20\).
• Subtask 3 (\(19\%\) số điểm): \(n \leq 1000\).
• Subtask 4 (\(17\%\) số điểm): \(m = n - 1\).
• Subtask 5 (\(12\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2
1 2 3
1 3
2 3

27

Với mỗi submission AC trong thời gian chính thức của contest LQDOJ Cup 2024 - Round #1, các bạn đã đóng góp 12.500 VNĐ vào quỹ ủng hộ đồng bào khắc phục sự cố cơn bão Yagi. Số tiền này sẽ được tổng hợp và chuyển tới Mặt trận Tổ quốc Việt Nam sau khi việc kiểm tra được hoàn tất.

Bạn Trung có \(n\) viên bi đầy màu sắc xếp thành một hàng, viên bi thứ \(i\) có màu \(a_i\), màu của một viên bi là một số nguyên dương có giá trị không quá \(1024\).

Độ đẹp của một hàng bi là độ dài dãy con liên tiếp dài nhất mà các viên bi trong dãy có cùng màu.

Bạn Trung có thể chọn một số viên bi bất kì trong hàng và đưa chúng ra khỏi hàng bi (các viên bi còn lại được giữ nguyên vị trí) sao cho các viên bị đưa ra ngoài thuộc không quá \(k\) màu khác nhau.

Hãy giúp bạn Trung tìm độ đẹp lớn nhất có thể của hàng bi.

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương \((1 \leq n \leq 131072, 1 \leq k \leq 1024)\) - độ dài của hàng bi và số lượng màu riêng biệt tối đa của các viên bi bị đưa ra khỏi hàng.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 1024)\) - màu của các viên bi.

Output

• Số nguyên duy nhất là độ đẹp lớn nhất có thể của hàng bi.

Scoring

• Subtask \(1\) (\(11\%\) số điểm): \(k = 1, n \leq 128\).
• Subtask \(2\) (\(12\%\) số điểm): \(k = 2\), có tối đa \(8\) màu.
• Subtask \(3\) (\(13\%\) số điểm): \(n \leq 512\), có tối đa \(16\) màu.
• Subtask \(4\) (\(15\%\) số điểm): \(n \leq 512\).
• Subtask \(5\) (\(16\%\) số điểm): \(n \leq 8192\).
• Subtask \(6\) (\(16\%\) số điểm): có tối đa \(64\) màu.
• Subtask \(7\) (\(17\%\) số điểm): không có rằng buộc gì thêm.

Example

5 1
1 3 3 2 3

3

10 2
2 3 1 4 4 1 2 2 4 3

3

22 3
3 3 3 3 2 1 1 1 4 5 1 1 1 3 3 6 7 10 3 3 3 3

6

Với mỗi submission AC trong thời gian chính thức của contest LQDOJ Cup 2024 - Round #1, các bạn đã đóng góp 12.500 VNĐ vào quỹ ủng hộ đồng bào khắc phục sự cố cơn bão Yagi. Số tiền này sẽ được tổng hợp và chuyển tới Mặt trận Tổ quốc Việt Nam sau khi việc kiểm tra được hoàn tất.

Khánh là một nhà một nhà khoa học tài ba, chuyên nghiên cứu về đồ thị, đặc biệt là cây.

Hôm nay Khánh đang tìm hiểu về một đồ thị vô hướng gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\), các đỉnh được nối với nhau bằng \(n - 1\) cạnh có trọng số ban đầu là \(0\) sao cho từ một đỉnh có thể đi đến tất cả các đỉnh còn lại.

Bây giờ Khánh có \(q\) truy vấn cập nhật trọng số các cạnh trên đồ thị, các truy vấn được đánh số lần lượt từ \(1\) đến \(q\). Mỗi truy vấn có dạng \(u\) \(v\) \(k\), tức là tăng trọng số các cạnh trên đường đi ngắn nhất từ \(u\) đến \(v\) lên \(k\) đơn vị. Ngoài ra ban đầu anh còn nắm giữ một số nguyên dương \(m\).

Khánh sẽ thực hiện \(t\) kịch bản, ở mỗi kịch bản anh sẽ chỉ thực hiện các truy vấn có chỉ số từ \(l\) đến \(r\), sau khi hoàn thành các truy vấn nêu trên anh muốn chọn \(m\) con đường liên thông với nhau sao cho tổng trọng số của \(m\) con đường ấy là lớn nhất.

Lưu ý rằng các kịch bản là độc lập với nhau, tức là mỗi kịch bản không ảnh hưởng đến các kịch bản khác. Trong mỗi kịch bản, ban đầu, trọng số của tất cả các cạnh bằng \(0\).

Yêu cầu: Với mỗi kịch bản, các bạn hãy tính tổng trọng số lớn nhất của \(m\) con đường liên thông.

Input

• Dòng đầu tiên chứa các số nguyên \(n, q, t\) và \(m\) \((2 \leq n \leq 10^{5}, 1 \leq q \leq 5 \times 10^{5}, 1 \leq t \leq 200, 1 \le m \leq min(n-1, 8)\)).
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) mô tả một cạnh của đồ thị.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u\), \(v\) và \(k\) \((1 \leq u, v \leq n, 1 \leq k \leq 100)\) mô tả truy vấn truy vấn thứ \(i\).
• Trong \(t\) dòng cuối cùng, dòng thứ \(i\) chứa hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq q)\) mô tả một kịch bản.

Output

• In ra \(t\) dòng là đáp án cho \(t\) kịch bản.

Scoring

• Subtask \(1\) (\(26\%\) số điểm): \(n \leq 15\).
• Subtask \(2\) (\(22\%\) số điểm): với mọi truy vấn, \(u\) và \(v\) là \(2\) đỉnh có cạnh nối trực tiếp.
• Subtask \(3\) (\(20\%\) số điểm): \(m \leq 3\)
• Subtask \(4\) (\(17\%\) số điểm): \(q \leq 10^{4}\)
• Subtask \(5\) (\(15\%\) số điểm): không có rằng buộc gì thêm.

Example

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

4
26
25
15