Subtask 1

Với \(n\) và \(m\) nhỏ, ta có thể có rất nhiều cách chạy trâu khác nhau. Cách đơn giản nhất chính là với mỗi đỉnh \(i\), ta sẽ duyệt qua các phương tiện và kiểm tra xem liệu trạm kiểm soát \(i\) có thuộc đường đi từ \(s_j\) tới \(t_j\) không.

Độ phức tạp: \(O(n^2 \cdot m)\).

Ý tưởng chung

Thay vì với mỗi trạm kiểm soát \(i\) ta cần tìm những phương tiện đi qua \(i\) phù hợp, ta sẽ làm ngược lại như sau: Với mỗi phương tiện, ta sẽ tìm xem những trạm kiểm soát nào có thể thu tiền từ phương tiện đó. Dễ dàng nhận thấy đó là các đỉnh thuộc đường đi từ \(s_j\) tới \(t_j\) và có tải trọng nhỏ hơn \(w_j\).

Giả sử đề bài có dạng như subtask 3, tức là xe \(i\) đi qua trạm nào cũng phải trả \(w_i\). Ta sẽ có một thuật toán để giải bài này như sau:

Ta sẽ đưa các trạm kiểm soát và các chuyến xe vào chung một danh sách, sắp xếp giảm dần theo tải trọng và duyệt qua danh sách này. Ta sẽ duy trì một mảng \(res\) với \(res[i]\) là số tiền trạm kiểm soát \(i\) thu được. Khi duyệt tới chuyến xe \(j\), ta sẽ tăng \(res[x]\) thêm một lượng bằng \(w_j\) với \(x\) là các đỉnh thuộc đường đi từ \(s_j\) tới \(t_j\). Khi duyệt tới trạm kiểm soát \(i\) nào đấy, ta sẽ chỉ cần đơn thuần in ra \(res[i]\) là xong, bởi vì khi đó tất cả các phương tiện có thể đi qua \(i\) đều đã được duyệt (vì sắp xếp giảm dần theo tải trọng).

Quay trở lại bài toán ban đầu, nếu áp dụng y nguyên thuật toán nêu trên vào bài toán gốc, ta nhận thấy các trạm kiểm soát sẽ thu tiền nhiều hơn so với thực tế. Do đó, ta sẽ cần phải "thối lại" lượng tiền dư ra. Giả sử một trạm kiểm soát \(i\) có \(k\) phương tiện đi qua lần lượt là \(h_1, h_2,\ldots,h_k\) thì \(res[i]=w_{h_1} +w_{h_2}+ \ldots +w_{h_k}\) trong khi lượng tiền thực tế cần thu sẽ là \(w_{h_1} - l_i+w_{h_2} - l_i+\ldots+w_{h_k}-l_i=w_{h_1} +w_{h_2}+ \ldots +w_{h_k}-k\cdot l_i=res[i]-l_i\cdot k\). Vì vậy ta sẽ cần "thối lại" tổng số tiền là \(l_i \cdot k\) với \(k\) là số phương tiện đi qua \(i\). Để tính được \(k\) của mỗi trạm \(i\), ta cũng sẽ làm tương tự: khi duyệt tới phương tiện \(j\), ta sẽ tăng \(k_x\) thêm \(1\) với \(x\) là các đỉnh thuộc đường đi từ \(s_j\) tới \(t_j\).

Vấn đề còn lại của chúng ta sẽ là thực hiện hai thao tác gồm tăng đường đi từ u tới u thêm k và lấy giá trị đỉnh u hiện tại một cách hiệu quả. Các subtask từ đây trở đi đều sẽ là để phục vụ việc giải bài toán này.

Subtask 2

Với thành phố dạng đường thẳng, thao tác tăng đường đi từ \(u\) tới \(v\) sẽ chỉ đơn thuần là tăng một đoạn liên tiếp. Ta có thể giải bằng cách sử dụng cấu trúc dữ liệu BIT (lưu ý rằng sử dụng Segment Tree Lazy có thể không đủ nhanh).

Độ phức tạp: \(O((n + m) \cdot \log (n + m))\).

Subtask 3

Các trạm kiểm soát đều có giới hạn là \(0\) đồng nghĩa với việc các truy vấn cập nhật đường đi sẽ được thực hiện toàn bộ trước các truy vấn lấy giá trị.

Ta sẽ xét bài toàn tương tự bài toán nêu trên, chỉ khác ở chỗ truy vấn tăng đường đi sẽ chỉ là tăng đường đi từ đỉnh \(1\) (đỉnh gốc) tới đỉnh \(u\) nào đấy thêm \(k\). Ta sẽ duy trì một mảng \(val[i]\). Với mỗi truy vấn tăng đường đi từ \(1\) tới \(u\) thêm, ta sẽ tăng \(val[u]\) thêm \(k\). Dễ dàng nhận thấy giá trị của một đỉnh \(u\) chính là tổng \(val[v]\) với \(v\) là các đỉnh thuộc cây con gốc \(u\). Với việc các truy vấn cập nhật thực hiện trước các truy vấn lấy giá trị, ta có thể đơn thuần tăng mảng \(val\), sau đó DFS tiền xử lý để tính giá trị các đỉnh.

Quay trở lại bài toán ban đầu là tăng đoạn từ \(u\) với \(v\) thêm \(k\), ta có thể biến đổi thao tác này thành các thao tác tăng đoạn từ \(1\) (đỉnh gốc) tới một đỉnh \(u\) thêm \(k\) như sau:

• Tăng đoạn từ \(1\) tới \(u\) thêm \(k\).
• Tăng đoạn từ \(1\) tới \(v\) thêm \(k\).
• Tăng đoạn từ \(1\) tới \(lca(u,v)\) thêm \(-k\).
• Tăng đoạn từ \(1\) tới cha trực tiếp của \(lca(u,v)\) (nếu có) thêm \(-k\).

Độ phức tạp: \(O((n + m) \cdot \log n)\).

Subtask 4

Ở subtask cuối, ta sẽ cần phải xử lý xen kẽ 2 loại truy vấn đã nêu. Ta có thể sử dụng topo sort. Gọi \(order[i]\) là thứ tự duyệt tới đỉnh \(i\) lần đầu tiên khi ta DFS từ đỉnh \(1\) (gốc). Khi đó tập hợp các đỉnh thuộc cây con gốc \(u\) sẽ có \(order\) từ \(order[u]\) tới \(max(order[v])\) với \(v\) là các đỉnh thuộc cây con gốc \(u\). Do đó, ta chuyển việc lấy tổng giá trị các đỉnh thuộc cây con gốc \(u\) trở thành lấy tổng của một đoạn liên tiếp.

Độ phức tạp: \(O((n+m) \cdot \log n)\).