CEOI 2020 - Day 2

Mỗi pháp sư sống tại một độ cao \(H_i\) khác nhau. Khoảng cách giữa hai độ cao là trị tuyệt đối của hiệu giữa chúng.

Một lời nguyền khiến các pháp sư không còn tin tưởng nhau. Ban đầu, không cặp pháp sư nào tin tưởng nhau. Cuối mỗi ngày, đúng một cặp pháp sư bắt đầu hoặc ngừng tin tưởng nhau. Tại mọi thời điểm, mỗi pháp sư tin tưởng không quá \(D\) người khác. Ta biết cặp pháp sư thay đổi quan hệ vào cuối từng ngày.

Kẻ trộm đã nói công thức của một lọ thuốc cho một pháp sư xấu xa vào ngày \(V\). Kẻ trộm đến thăm nhà một người bạn mà mình tin tưởng, còn pháp sư xấu xa đến thăm nhà một người bạn mà người đó tin tưởng. Hai người bạn này có thể là cùng một người, và cũng có thể chính họ đã đến thăm nhà của nhau.

Với mỗi giả thuyết rằng kẻ trộm là \(X\), pháp sư xấu xa là \(Y\), và lời thì thầm được truyền vào ngày \(V\), hãy tìm khoảng cách nhỏ nhất mà lời thì thầm phải truyền qua. Cụ thể, lấy nhỏ nhất \(|H_{X'}-H_{Y'}|\) trên mọi cặp \(X',Y'\) sao cho vào ngày \(V\), \(X'\) được \(X\) tin tưởng và \(Y'\) được \(Y\) tin tưởng. Nếu \(X'=Y'\), khoảng cách là \(0\). Nếu \(X\) hoặc \(Y\) không tin tưởng ai vào ngày đó, câu trả lời là \(10^9\).

LQDOJ cung cấp toàn bộ lịch sử thay đổi và các câu hỏi trong dữ liệu vào. Hãy trả lời các câu hỏi theo đúng thứ tự.

Dữ liệu vào

Dòng đầu gồm bốn số nguyên \(N,D,U,Q\): số pháp sư, giới hạn số người được tin tưởng, số ngày có thay đổi và số câu hỏi.

Dòng thứ hai gồm \(N\) số nguyên \(H_i\).

Mỗi dòng trong \(U\) dòng tiếp theo gồm hai số nguyên \(A_i,B_i\), là cặp pháp sư có quan hệ tin tưởng bắt đầu hoặc kết thúc vào cuối ngày \(i\).

Mỗi dòng trong \(Q\) dòng cuối gồm ba số nguyên \(X,Y,V\), là hai pháp sư trong giả thuyết và ngày cần xét.

Các chỉ số pháp sư bắt đầu từ \(0\). Ở ngày \(0\), chưa có cặp nào tin tưởng nhau. Cặp \((A_i,B_i)\) thay đổi trạng thái từ ngày \(i\) sang ngày \(i+1\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) là khoảng cách nhỏ nhất ứng với câu hỏi thứ \(i\).

Ví dụ

6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4
3 0 8
0 5 5
3 0 11

26
0
1000000000
14

Hình dưới minh họa bốn câu hỏi trong ví dụ.

Hình tiếp theo minh họa các quan hệ tin tưởng thay đổi qua từng ngày.

Ràng buộc

• \(2\le N\le10^5\).
• \(1\le D\le500\).
• \(0\le U\le2\cdot10^5\).
• \(1\le Q\le5\cdot10^4\).
• \(0\le H_i\le10^9\).
• \(0\le A_i,B_i,X,Y<N\).
• \(X\ne Y\) và \(A_i\ne B_i\).
• Mọi thay đổi đều bảo đảm mỗi pháp sư tin tưởng không quá \(D\) người tại bất kỳ thời điểm nào.
• Các giá trị \(A_i,B_i\) xác định đúng một cặp bắt đầu hoặc ngừng tin tưởng nhau.
• \(0\le V\le U\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(17\) điểm: \(Q,U\le1000\).
3. \(14\) điểm: \(V=U\) trong mọi câu hỏi.
4. \(18\) điểm: \(H_i\in\{0,1\}\) với mọi \(i\).
5. \(21\) điểm: \(U,N\le10000\).
6. \(30\) điểm: Không có ràng buộc nào khác.

Flóra và mẹ tìm thấy một cây phủ đầy bụi dưới tấm thảm. Cây có \(N\) đỉnh được đánh số từ \(1\) đến \(N\), nối với nhau bằng \(N-1\) cạnh.

Để làm sạch cây, mẹ của Flóra lặp lại thao tác sau: chọn hai lá khác nhau rồi làm sạch tất cả các cạnh trên đường đi ngắn nhất giữa hai lá đó. Một đỉnh là lá nếu nó có đúng một cạnh nối với đỉnh khác. Nếu đường đi có \(d\) cạnh thì chi phí làm sạch đường đi là \(d\). Cây được làm sạch khi mọi cạnh đã được làm sạch; tổng chi phí là tổng chi phí của các đường đi đã chọn. Mỗi lá chỉ được chọn làm đầu mút nhiều nhất một lần.

Flóra xét \(Q\) phiên bản của cây ban đầu. Trong phiên bản thứ \(i\), cô thêm tổng cộng \(D_i\) lá mới. Mỗi lá mới được tạo bằng cách chọn một đỉnh của cây ban đầu và nối đỉnh đó với lá mới bằng một cạnh. Có thể thêm nhiều lá vào cùng một đỉnh. Trong quá trình thêm lá, một số đỉnh ban đầu có thể không còn là lá.

Mỗi phiên bản bắt đầu lại từ cây ban đầu. Với từng phiên bản, hãy tìm chi phí nhỏ nhất để làm sạch toàn bộ cây. Nếu không thể làm sạch cây, in \(-1\).

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N,Q\).

Mỗi dòng trong \(N-1\) dòng tiếp theo gồm hai số nguyên \(u,v\), cho biết có một cạnh nối hai đỉnh \(u\) và \(v\) trong cây ban đầu.

Mỗi phiên bản được mô tả trên một dòng. Số đầu tiên là \(D_i\), tiếp theo là \(D_i\) số nguyên \(a_j\); mỗi số cho biết có một lá mới được nối với đỉnh \(a_j\) của cây ban đầu.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) là chi phí nhỏ nhất để làm sạch phiên bản thứ \(i\), hoặc \(-1\) nếu không thể.

Ví dụ

7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1

-1
10
8

Ràng buộc

• \(3\le N\le10^5\).
• \(1\le Q\le10^5\).
• \(1\le u,v\le N\).
• \(1\le D_i\le10^5\) với mọi \(i\).
• \(\sum_{i=1}^{Q}D_i\le10^5\).
• \(1\le a_j\le N\) với mọi lá được thêm.

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(9\) điểm: \(Q=1\), cây ban đầu là hình sao tâm \(1\) (có cạnh nối \(1\) với mọi đỉnh \(2,3,\ldots,N\)), và không thêm lá nào vào đỉnh \(1\).
3. \(9\) điểm: \(Q=1\), cây ban đầu là đường đi \(1-2-\cdots-N\), và không thêm lá nào vào đỉnh \(1\) hoặc đỉnh \(N\).
4. \(16\) điểm: \(N\le20000\) và \(Q\le300\).
5. \(19\) điểm: Cây ban đầu là cây nhị phân hoàn hảo có gốc tại đỉnh \(1\): mỗi đỉnh trong có đúng hai con và mọi lá cách gốc cùng một khoảng cách.
6. \(17\) điểm: \(D_i=1\) với mọi \(i\).
7. \(30\) điểm: Không có ràng buộc nào khác.

Chess Land là một bàn cờ hình chữ nhật gồm \(R\) hàng và \(C\) cột, trong đó \(R\ge C\). Các hàng được đánh số từ \(1\) đến \(R\), các cột được đánh số từ \(1\) đến \(C\).

Ở đây có năm loại quân cờ: tốt, xe, tượng, hậu và vua; không có quân mã. Trong một nước đi:

• Tốt đi lên một hàng, từ hàng \(r\) sang hàng \(r+1\), không đổi cột.
• Xe đi tùy ý số ô theo hàng hoặc theo cột.
• Tượng đi đến một ô bất kỳ trên một trong hai đường chéo đi qua ô hiện tại.
• Hậu có thể đi như xe hoặc như tượng.
• Vua đi đến một trong tám ô kề cạnh hoặc kề góc.

Hình dưới đánh dấu bằng chữ X các ô mà mỗi quân có thể đi tới trong một nước. Trong hình, các hàng được đánh số từ dưới lên và các cột từ trái sang phải.

Quân cờ có thể bị bắt bất ngờ khi đang đi qua bàn cờ và biến mất. Vì vậy, mỗi quân muốn tới đích với số nước đi ít nhất có thể; trong số các cách dùng ít nước nhất, ta cũng cần đếm số đường đi khác nhau. Hai đường đi khác nhau nếu chúng có ít nhất một ô được ghé thăm khác nhau.

Mỗi câu hỏi cho biết loại quân, cột xuất phát ở hàng \(1\) và cột đích ở hàng \(R\). Hãy tìm số nước đi ít nhất và số đường đi đạt được số nước đi đó. Nếu không thể tới ô đích, in 0 0.

Số đường đi cần được tính modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu gồm ba số nguyên \(R,C,Q\): số hàng, số cột và số câu hỏi.

Mỗi dòng trong \(Q\) dòng tiếp theo gồm một ký tự \(T\) và hai số nguyên \(c_1,c_R\). Ký tự \(T\) là loại quân (P là tốt, R là xe, B là tượng, Q là hậu, K là vua); \(c_1\) là cột xuất phát ở hàng \(1\), còn \(c_R\) là cột cần tới ở hàng \(R\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) gồm hai số nguyên: số nước đi ít nhất và số đường đi dùng số nước ít nhất cho câu hỏi thứ \(i\). Số đường đi phải được lấy modulo \(10^9+7\).

Ví dụ

8 8 5
P 1 2
R 4 8
Q 2 3
B 3 6
K 5 5

0 0
2 2
2 5
2 2
7 393

Ràng buộc

• \(1\le Q\le1000\).
• \(2\le C\le1000\).
• \(C\le R\le10^9\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(8\) điểm: Mọi câu hỏi đều hỏi về tốt, xe hoặc hậu.
3. \(15\) điểm: Mọi câu hỏi đều hỏi về tượng; \(C,R\le100\).
4. \(22\) điểm: Mọi câu hỏi đều hỏi về tượng.
5. \(5\) điểm: Mọi câu hỏi đều hỏi về vua; \(C,R\le100\) và \(Q\le50\).
6. \(8\) điểm: Mọi câu hỏi đều hỏi về vua; \(C,R\le100\).
7. \(15\) điểm: Mọi câu hỏi đều hỏi về vua; \(C\le100\).
8. \(20\) điểm: Mọi câu hỏi đều hỏi về vua.
9. \(7\) điểm: Không có ràng buộc nào khác.