APIOBike là một dịch vụ chia sẻ xe đạp mới được ra mắt tại thành phố APIO. Một vài trạm được lắp đặt khắp thành phố, giúp cho người dùng có thể mượn hoặc trả xe ở bất kỳ trạm nào. Bởi sự tiện dụng và chi phí thấp, nó đã nhanh chóng trở thành phương tiện di chuyển quan trọng nhất trong thành phố APIO. Tuy nhiên, APIOBike đã gặp phải một vấn đề thường gặp của tất cả các hãng dịch vụ chia sẻ xe: sự mất cân bằng giữa tỷ lệ mượn và trả ở những trạm khác nhau. Kết quả là một số trạm có ít xe đạp, làm cho cư dân xung quanh không thể mượn xe; một số trạm lại có quá nhiều xe, những xe thừa mà người dân xung quanh không cần.

Để giải quyết vấn đề này, APIOBike lên kế hoạch điều động một xe tải tái cân bằng mỗi đêm để phân bổ lại xe đạp giữa các trạm, đảm bảo mỗi trạm đều duy trì số lượng xe đạp phù hợp. Thành phố APIO có toàn bộ \(N\) trạm, đánh số \(0, 1, \ldots, N-1\). Thông qua quan sát, APIOBike nhận ra rằng mỗi tối, số lượng xe đạp ở trạm \(i\) luôn có giá trị \(A[i]\), và không ai mượn hoặc trả xe vào buổi tối. Công ty muốn có đúng \(B[i]\) xe ở trạm \(i\) vào mỗi sáng.

Giữa \(N\) trạm, có \(N-1\) con đường được dành cho xe tải tái cân bằng. Mỗi con đường nối giữa hai trạm khác nhau, và xe tải chỉ sử dụng những con đường này để di chuyển. Mỗi con đường có độ dài là một đơn vị. Mạng lưới trạm là liên thông, đảm bảo rằng xe tải có thể di chuyển giữa bất kỳ cặp trạm nào. Mỗi đêm, APIOBike phải điều động một xe tải tái cân bằng để đảm bảo trạm \(i\) có đúng \(B[i]\) xe. Xe tải này có thể bắt đầu ở bất kỳ trạm nào và kết thúc đường đi của nó ở bất kỳ trạm nào.

Xe tải này là rỗng khi bắt đầu quá trình cân bằng. Bất cứ khi nào xe tải ở tại một trạm, người lái xe có thể bốc bất kỳ số lượng xe đạp nào từ trạm lên xe tải, hoặc dỡ bất kỳ số lượng xe đạp nào từ xe tải xuống trạm. Xe tải và các trạm không có giới hạn sức chứa cho xe đạp nhưng số lượng xe đạp ở bất kỳ địa điểm nào phải không bao giờ xuống dưới không. Công ty muốn xác định khoảng cách di chuyển tối thiểu có thể để hoàn thành việc tái cân bằng và chiến lược tương ứng.

Chi tiết cài đặt

Bạn cần xây dựng hàm sau (khai báo trong bike.h):

std::pair<std::vector<int>, std::vector<long long>>
find_rebalancing_strategy(int N,
                          std::vector<int> A,
                          std::vector<int> B,
                          std::vector<int> U,
                          std::vector<int> V)

Tham số:

• \(N\): số lượng trạm.
• \(A\): một mảng có độ dài \(N\), trong đó \(A[i]\) là số lượng xe đạp tại trạm \(i\) mỗi buổi tối.
• \(B\): một mảng có độ dài \(N\), trong đó \(B[i]\) là số lượng xe đạp mục tiêu tại trạm \(i\) mỗi sáng.
• \(U\), \(V\): các mảng có độ dài \(N-1\) biểu thị mạng lưới đường bộ. Với mỗi \(0 \le i < N-1\), con đường thứ \(i\) kết nối trạm \(U[i]\) và trạm \(V[i]\).

Hàm này được gọi tối đa 150 000 lần với mỗi trường hợp thử nghiệm.

Giá trị trả về:

Hàm này cần trả về một cặp mảng \((X, Y)\) có độ dài bằng nhau là \(k+1\), biểu thị một chiến lược tái cân bằng:

• \(X\): chuỗi chỉ số các trạm được ghé thăm theo thứ tự thời gian.
• \(Y\): tổng số xe được vận chuyển ở mỗi trạm ghé thăm. Với mỗi \(0 \le j \le k\):
• Nếu \(Y[j] \ge 0\), tài xế dỡ xuống \(Y[j]\) xe đạp ở trạm \(X[j]\) từ xe tải, tăng số lượng xe của trạm lên \(Y[j]\).
• Nếu \(Y[j] < 0\), tài xế bốc lên \(-Y[j]\) xe đạp từ trạm \(X[j]\) lên xe tải, giảm số lượng xe của trạm đi \(-Y[j]\).

Một chiến thuật tái cân bằng hợp lệ \((X, Y)\) với khoảng cách di chuyển \(k\) phải thỏa mãn những điều kiện sau:

• Với mỗi \(0 \le j \le k\): \(0 \le X[j] < N\).
• Với mỗi \(0 \le j < k\): trạm \(X[j]\) và trạm \(X[j+1]\) được nối bởi một con đường.
• Với mỗi \(0 \le j \le k\): \(\sum_{t=0}^{j} Y[t] \le 0\).
• Với mỗi trạm \(0 \le i < N\) và mỗi bước \(0 \le j \le k\), gọi \(S_{i,j}\) là tổng của \(Y[t]\) qua tất cả các bước \(t\) mà \(0 \le t \le j\) và \(X[t] = i\):
• Số lượng xe tại trạm \(i\) không bao giờ xuống dưới không: \(A[i] + S_{i,j} \ge 0\).
• Sau khi chiến thuật được hoàn thành, mỗi trạm \(i\) phải có đúng \(B[i]\) xe đạp: \(A[i] + S_{i,k} = B[i]\).

Ràng buộc

• \(2 \le N \le 300\,000\)
• Tổng các \(N\) qua tất cả lời gọi đến hàm find_rebalancing_strategy không vượt quá \(300\,000\) với mỗi trường hợp thử nghiệm.
• \(0 \le U[i], V[i] < N\) và \(U[i] \ne V[i]\) với mỗi \(i\) sao cho \(0 \le i < N\).
• \(0 \le A[i], B[i] \le 10^9\) với mỗi \(i\) sao cho \(0 \le i < N\).
• Có thể di chuyển giữa bất kỳ cặp trạm nào.
• \(\sum_{i=0}^{N-1} A[i] = \sum_{i=0}^{N-1} B[i]\).
• Tồn tại ít nhất một giá trị \(i\) sao cho \(0 \le i < N\) và \(A[i] \ne B[i]\).

Phân nhóm

Ở đây, \(T\) là số lần gọi hàm find_rebalancing_strategy, và \(\sum N\) là tổng các \(N\) qua tất cả lời gọi đến hàm find_rebalancing_strategy.

Tính chất P: Với mỗi \(0 \le i < N-1\), \(U[i] = i\) và \(V[i] = i+1\). Với mỗi \(0 \le i < N\), \(A[i] \ne B[i]\).

• Subtask 1 (4 điểm): Các trạm và các con đường thỏa mãn tính chất P. Tồn tại duy nhất một \(i\) sao cho \(0 \le i < N\) và \(A[i] > 0\).
• Subtask 2 (11 điểm): \(T \le 10\). \(N \le 7\). Các trạm và các con đường thỏa mãn tính chất P.
• Subtask 3 (16 điểm): Các trạm và các con đường thỏa mãn tính chất P.
• Subtask 4 (9 điểm): Tồn tại duy nhất một \(i\) sao cho \(0 \le i < N\) và \(A[i] > 0\).
• Subtask 5 (24 điểm): \(\sum N \le 500\).
• Subtask 6 (15 điểm): \(\sum N \le 5000\).
• Subtask 7 (21 điểm): Không có ràng buộc nào thêm.

Ví dụ

1
4
10 1 5 0
10 0 3 3
0 1
1 2
1 3

2
2 1 3
-2 -1 3

1
5
3 0 1 2 2
2 2 1 3 0
2 0
2 4
2 3
2 1

6
0 2 1 2 4 2 3
-1 -1 2 0 -2 1 1

1
4
3 0 5 0
2 2 3 1
0 1
1 2
2 3

5
2 1 0 1 2 3
-1 1 -1 1 -1 1

Chấm điểm

Đây là bài toán dạng Batch với signature grader (bike.h). Hàm find_rebalancing_strategy của bạn sẽ được gọi tối đa 150 000 lần trong một test case.

Nếu mảng trả về \(X\) và \(Y\) có độ dài chính xác là \(k^* + 1\), trong đó \(k^*\) là khoảng cách di chuyển tối thiểu có thể, nhưng \((X, Y)\) không phải là một chiến lược hợp lệ, bạn sẽ nhận được 50% điểm số của subtask đó.