LQDOJ Cup 2024 - Round #8

Hoàng đang lạc ở một dãy núi và cần thoát ra khỏi nơi này. Dãy núi này gồm \(n+2\) đỉnh núi được đánh chỉ số từ \(0\) đến \(n+1\). Hoàng đang ở đỉnh núi \(0\) và cần di chuyển đến đỉnh núi \(n+1\) để đi cáp treo xuống núi. Vì các đỉnh núi gần nhau nên Hoàng có thể nhảy từ đỉnh núi \(i\) đến đỉnh núi \(j\) nếu \(0 < j-i \leq k\). Tuy nhiên, với mỗi đỉnh núi từ \(1\) đến \(n\), đỉnh núi thứ \(i\) có độ cao \(a_i\) và độ trơn trượt \(b_i\). Độ nguy hiểm của việc di chuyển từ đỉnh núi \(0\) đến đỉnh núi \(n+1\) là \(max(a_x)\times max(b_y)\) với \(x,y\) là chỉ số những đỉnh núi trong khoảng từ \(1\) đến \(n\) mà Hoàng nhảy đến. Nếu độ nguy hiểm quá cao, Hoàng sẽ bị trượt chân ngã xuống vách núi. Hãy giúp Hoàng tìm cách nhảy để có thể đến đỉnh núi \(n+1\) với độ nguy hiểm nhỏ nhất có thể.

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(k\) \((1\leq k\leq n \leq 5 \times 10^5)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số nguyên dương \(a_i,b_i\) \((1 \leq a_i, b_i \leq 10^9)\) miêu tả đỉnh núi thứ \(i\).

Output

• Độ nguy hiểm nhỏ nhất có thể để có thể đi đến đỉnh núi \(n+1\).

Scoring

• Subtask \(1\) (\(21\%\) số điểm): \(1 \leq n \leq 20\).
• Subtask \(2\) (\(23\%\) số điểm): \(1 \leq n,a_i \leq 100\).
• Subtask \(3\) (\(27\%\) số điểm): \(1 \leq n\leq 3000\).
• Subtask \(4\) (\(29\%\) số điểm): Không có điều kiên gì thêm.

Example

5 3
2 2
5 7
7 3
9 9
5 1

21

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

36

Bạn được cho một cây gồm \(n\) đỉnh và \(m\) yêu cầu, mỗi yêu cầu là một đường đi trên cây từ \(u\) đến \(v\). Bạn phải tô mỗi cạnh trên cây bằng một màu từ \(1\) đến \(K\) sao cho với mỗi yêu cầu, đường đi của yêu cầu phải có ít nhất hai màu khác nhau.

Yêu cầu: Đếm số cách tô màu hợp lệ, hai cách tô màu được coi là khác nhau nếu tồn tại một cạnh có màu khác nhau trong hai cách.

Input

• Dòng đầu chứa ba số nguyên dương \(n, m\) và \(k\) \((1 \le n \le 70, 1 \le m \le 15, 1 \le k \le 10^9)\).
• \(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 cây.
• \(m\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(x\) và \(y\) \((1 \leq x, y \leq n)\) mô tả một yêu cầu.

Output

• Một số nguyên là số cách tô màu hợp lệ --- Kết quả của bài toán lấy phần dư khi chia cho \(10 ^ 9 + 7\).

Scoring

• Subtask 1 (\(20\%\) số điểm): \(m = 1\).
• Subtask 2 (\(20\%\) số điểm): \(m = 2\).
• Subtask 3 (\(20\%\) số điểm): Mỗi cạnh trên cây thuộc không quá \(1\) yêu cầu.
• Subtask 4 (\(20\%\) số điểm): \(k = 2\).
• Subtask 5 (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 1 3
1 2
2 3
1 3

6

Hôm nay Khánh, nhà khoa học đại tài đã lập trình chương trình phân tích xâu. Chương trình của Khánh hoạt động như sau:

• Ban đầu, chương trình có \(n\) xâu không rỗng được đánh số từ \(1\) đến \(n\), mỗi xâu gồm các chữ cái latin viết hoa có tổng độ dài không quá \(2 \times 10^5\) và mỗi xâu có một giá trị nguyên dương \(v_i\).
• Tiếp đó, chương trình sẽ thực hiện lần lượt \(q\) truy vấn, mỗi truy vấn thuộc một trong \(2\) dạng:
  • \(1\) \(x\) \(k\): truy vấn này sẽ gán giá trị của xâu thứ \(x\) thành \(k\).
  • \(2\) \(s\): cho xâu \(s\) gồm các chữ cái latin viết hoa, xét tất cả các xâu trong \(n\) xâu đã cho, gọi \(f_i\) là số lần xuất hiện của \(s\) dưới dạng xâu con liên tiếp của xâu thứ \(i\). Ta cần tính tổng \(f_i \times v_i\).

Bây giờ Khánh đố các bạn là với mỗi truy vấn loại \(2\) thì tổng \(f_i \times v_i\) là bao nhiêu?

Input

• Dòng đầu tiên lần lượt là \(2\) số nguyên dương \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).
• Dòng tiếp theo là giá trị các xâu \(v_1, v_2, ..., v_n\) (\(1\le v_i \le 10^6\) với \(1 \le i \le n\)).
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo là xâu thứ \(i\) trong \(n\) xâu ban đầu, tổng độ dài của \(n\) xâu này không quá \(2 \times 10^5\).
• \(q\) dòng tiếp theo, mỗi dòng biểu thị một truy vấn có dạng \(1\) \(x\) \(k\) (\(1 \le x \le n, 1 \le k \le 10^6\)) hoặc \(2\) \(s\), tổng độ dài các xâu của toàn bộ truy vấn \(2\) không quá \(2 \times 10^5\).

Output

• Với mỗi truy vấn loại \(2\) in ra kết quả trên một dòng.

Scoring

• Subtask 1 (\(18\%\) số điểm): tổng độ dài các xâu trong \(n\) xâu ban đầu không quá \(10^3\), tổng độ dài các xâu trong toàn bộ truy vấn \(2\) không quá \(10^3\).
• Subtask 2 (\(19\%\) số điểm): \(n, q \le 10^3\).
• Subtask 3 (\(20\%\) số điểm): không có truy vấn loại \(1\).
• Subtask 4 (\(21\%\) số điểm): một xâu chỉ bị thay đổi giá trị tối đa \(1\) lần.
• Subtask 5 (\(22\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
1 1 1
ABABAA
AAAA
BABBBA
2 AB
2 AAA
1 1 3
2 AB 

3
2
7