Subtask \(1\) (\(20\) điểm): \(1 \leq N, M \leq 5 \times 10^{3}\).

Ở subtask này, với người cận vệ thứ \(i\), ta liệt kê các đỉnh nằm trên đường đi từ \(u_{i}\) đến \(v_{i}\) và cập nhật thời gian sớm nhất mà có người cận vệ đi đến các thành phố trên đường đi từ \(u_{i}\) đến \(v_{i}\).

Subtask \(2\) (\(18\) điểm): \(a_{i} = \left \lfloor \dfrac{i + 1}{2} \right \rfloor, b_{i} = i + 1, 1 \leq i \leq N - 1\).

Ở subtask này, bản đồ thành phố là 1 cây nhị phân nên đường đi từ \(u_{i}\) đến \(v_{i}\) có không quá \(2 \times \log_{2}(N)\) đỉnh nên ta có thể liệt kê các đỉnh từ \(u_{i}\) đến \(v_{i}\) bằng thuật toán tìm LCA rồi cập nhật như subtask \(1\)

Subtask \(3\) (\(16\) điểm): \(Q \le 10\).

Ở subtask này, với mỗi thành phố mà đức vua quan tâm, ta kiểm tra xem có những cận vệ nào đi qua thành phố đó và thời gian sớm nhất của cận vệ đi qua thành phố đó.

Subtask \(4\) (\(14\) điểm): \(s_1 = s_2 = \ldots = s_M\), \(v_{i} = 1\) \(\forall 1 \leq i \leq M\).

Nhận xét: Tốc độ của những người cận vệ bằng nhau và đều hướng về đỉnh 1

Gọi \(d_{i}\) là khoảng cách từ thành phố \(1\) đến thành phố \(i\). Với người cận vệ thứ \(j\) xuất phát từ thành phố \(u_{j}\) ta có phương trình là \(t_{j} + (d_{u_{j}} - x) * \dfrac{1}{s_{i}} = t_{j} + \dfrac{d_{u_{j}}}{s_{i}} - \dfrac{x}{s_{i}}\). Vì tất cả những người cận vệ đều đi về 1 nên ta có thể sử dụng kỹ thuật gộp set để tìm cận vệ đi từ trong cây con gốc \(u\) đến \(u\) sớm nhất.

Subtask \(5\) (\(12\) điểm): \(s_1 = s_2 = \ldots = s_M\).

Vì tốc độ của những người cặn vệ bằng nhau nên ta vẫn có thể sử dụng gộp set để giải quyết subtask này.

Gọi \(p_{j}\) là tổ tiên chung gần nhất của \(u_{i}\) đến \(v_{i}\). ta chia đường đi từ \(u_{i}\) đến \(v_{i}\) thành 2 chặng là \(u_{i}\) đến \(p_{i}\) và \(p_{i}\) đến \(v_{i}\).

• Với đường đi từ \(u_{i}\) đến \(p_{i}\) ta sử dụng công thức \(t_{j} + (d_{u_{j}} - x) * \dfrac{1}{s_{i}} = t_{j} + \dfrac{d_{u_{j}}}{s_{i}} - \dfrac{x}{s_{i}}\).
• Với đường đi từ \(p_{i}\) đến \(v_{i}\) ta có công thức \(t_{j} + \dfrac{dist(u, v)}{s_{i}} - (d_{v_{j}} - x) * \dfrac{1}{s_{i}} = t_{j} + \dfrac{dist(u, v) - d_{v_{j}}}{s_{i}} + \dfrac{x}{s_{i}}\).

Ta chia ra hai trường hợp dựa vào dấu của \(x\) rôi sử dụng gộp set để tính toán.

Subtask \(6\) (\(11\) điểm): Mỗi thành phố được kết nối trực tiếp với không quá hai con đường.

Ở subtask này, bản đồ thành phố là 1 đường thẳng còn thời gian của người cận vệ thứ i ta có thể biểu diễn bởi phương trình bậc nhất nên ta có thể sử dụng lichao tree để cập nhật và lấy giá trị nhỏ nhât.

Subtask \(7\) (\(9\) điểm): Không có ràng buộc gì thêm.

Ta vẫn sử dụng lichao tree để cập nhật ở subtask này, nhưng ta phải sử dụng phân rã cây HLD để chia cây thành các đường thẳng, và chia đường đi từ \(u_{i}\) đến \(v_{i}\) thành các chặng tương ứng và cập nhật trên Lichao tree.