Hungary là đất nước có \(N\) thành phố, đánh số từ \(0\) đến \(N-1\).

Các thành phố được nối với nhau bằng \(N-1\) con đường hai chiều, được đánh số từ \(0\) đến \(N-2\). Với mỗi \(j\) mà \(0 \le j \le N-2\), con đường \(j\) nối thành phố \(U[j]\) với thành phố \(V[j]\) và có độ dài \(W[j]\), nghĩa là một người đi giữa hai thành phố mất \(W[j]\) đơn vị thời gian. Mỗi con đường nối hai thành phố phân biệt và mỗi cặp thành phố được nối bởi nhiều nhất một con đường.

Một đường đi giữa hai thành phố phân biệt \(a\) và \(b\) là một chuỗi \(p_0,p_1,\ldots,p_t\) các thành phố khác nhau, sao cho:

• \(p_0=a\);
• \(p_t=b\);
• với mỗi \(i\) (\(0 \le i < t\)), có một con đường nối thành phố \(p_i\) và \(p_{i+1}\).

Có thể đi lại từ một thành phố bất kì đến một thành phố bất kì khác sử dụng các con đường, nghĩa là có một đường đi giữa hai thành phố phân biệt bất kì. Có thể chứng minh rằng đường đi này là duy nhất cho từng cặp thành phố phân biệt.

Độ dài của một đường đi \(p_0,p_1,\ldots,p_t\) là tổng độ dài của \(t\) con đường nối các thành phố liên tiếp nhau dọc theo đường đi đó.

Ở Hungary, nhiều người di chuyển để tham gia các lễ hội ngày Quốc khánh tại hai thành phố lớn. Khi các buổi ăn mừng kết thúc, họ quay trở về nhà. Chính quyền muốn tránh việc các đám đông làm phiền cư dân địa phương, nên dự định ra lệnh giới nghiêm ở tất cả các thành phố vào các thời điểm nhất định. Chính quyền gán cho mỗi thành phố một thời điểm đóng cửa không âm và quyết định rằng tổng các thời điểm đóng cửa không vượt quá \(K\). Cụ thể, với mỗi \(i\) từ \(0\) đến \(N-1\), thời điểm đóng cửa được gán cho thành phố \(i\) là số nguyên không âm \(c[i]\). Tổng của tất cả các số \(c[i]\) không vượt quá \(K\).

Xét thành phố \(a\) và một cách gán thời điểm đóng cửa. Ta nói thành phố \(b\) đến được từ thành phố \(a\) khi và chỉ khi hoặc \(b=a\), hoặc đường đi \(p_0,\ldots,p_t\) giữa hai thành phố này (nghĩa là \(p_0=a\) và \(p_t=b\)) thỏa mãn các điều kiện sau:

• độ dài đường đi \(p_0,p_1\) không vượt quá \(c[p_1]\), và
• độ dài đường đi \(p_0,p_1,p_2\) không vượt quá \(c[p_2]\), và
• \(\ldots\)
• độ dài đường đi \(p_0,p_1,p_2,\ldots,p_t\) không vượt quá \(c[p_t]\).

Trong năm nay, hai địa điểm chính tổ chức lễ hội đặt tại thành phố \(X\) và thành phố \(Y\). Với mỗi cách gán thời điểm đóng cửa, điểm thuận tiện được định nghĩa là tổng của hai số sau:

• Số lượng thành phố đến được từ thành phố \(X\).
• Số lượng thành phố đến được từ thành phố \(Y\).

Lưu ý rằng nếu một thành phố đến được từ thành phố \(X\) và cũng đến được từ thành phố \(Y\) thì thành phố đó được tính hai lần vào điểm thuận tiện.

Nhiệm vụ của bạn là tính điểm thuận tiện lớn nhất có thể đạt được bởi một cách gán thời điểm đóng cửa.

Chi tiết cài đặt

Bạn phải cài đặt hàm sau:

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W);

• \(N\): số lượng thành phố.
• \(X,Y\): hai thành phố có địa điểm chính tổ chức lễ hội.
• \(K\): cận trên của tổng thời điểm đóng cửa.
• \(U,V\): các mảng có kích thước \(N-1\) mô tả hai đầu của các con đường.
• \(W\): mảng có kích thước \(N-1\) mô tả độ dài các con đường.
• Hàm này phải trả về điểm thuận tiện lớn nhất có thể đạt được bởi một cách gán thời điểm đóng cửa.
• Hàm này có thể được gọi nhiều lần trong mỗi test.

Ví dụ

Xét lời gọi hàm sau:

max_score(7, 0, 2, 10,
          [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3])

Lời gọi này tương ứng với mạng lưới các con đường sau:

Giả sử các thời điểm đóng cửa được gán như sau:

Lưu ý rằng tổng thời điểm đóng cửa là \(9\), không vượt quá \(K=10\). Các thành phố \(0,1,3\) đến được từ thành phố \(X\) (\(X=0\)), trong khi các thành phố \(1,2,4\) đến được từ thành phố \(Y\) (\(Y=2\)). Vì thế, điểm thuận tiện là \(3+3=6\). Không có cách gán thời điểm đóng cửa nào có điểm thuận tiện lớn hơn \(6\), do đó hàm phải trả về \(6\).

Xét lời gọi hàm sau:

max_score(4, 0, 3, 20, [0, 1, 2], [1, 2, 3], [18, 1, 19])

Lời gọi này tương ứng với mạng lưới các con đường sau:

Giả sử các thời điểm đóng cửa được gán như sau:

Thành phố \(0\) đến được từ thành phố \(X\) (\(X=0\)), trong khi các thành phố \(2,3\) đến được từ thành phố \(Y\) (\(Y=3\)). Vì thế, điểm thuận tiện là \(1+2=3\). Không có cách gán thời điểm đóng cửa nào có điểm thuận tiện lớn hơn \(3\), do đó hàm phải trả về \(3\).

Các ràng buộc

• \(2 \le N \le 200\,000\).
• \(0 \le X < Y < N\).
• \(0 \le K \le 10^{18}\).
• \(0 \le U[j] < V[j] < N\) (với mỗi \(j\) mà \(0 \le j \le N-2\)).
• \(1 \le W[j] \le 10^6\) (với mỗi \(j\) mà \(0 \le j \le N-2\)).
• Có thể đi từ thành phố bất kì đến một thành phố bất kì khác sử dụng các con đường.
• \(S_N \le 200\,000\), với \(S_N\) là tổng các giá trị \(N\) trong tất cả lời gọi đến max_score trong mỗi test.

Các subtask

Ta nói một mạng lưới các con đường là đường thẳng nếu con đường \(i\) nối thành phố \(i\) và \(i+1\) (với mỗi \(i\) mà \(0 \le i \le N-2\)).

Trình chấm mẫu

Đặt \(C\) là số lượng kịch bản, tức là số lần gọi đến max_score. Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: C

Theo sau là mô tả của \(C\) kịch bản. Trình chấm mẫu đọc mô tả của từng kịch bản theo định dạng sau:

dòng 1: N X Y K
dòng 2 + j (0 ≤ j ≤ N − 2): U[j] V[j] W[j]

Trình chấm mẫu in một dòng duy nhất cho từng kịch bản theo định dạng sau:

dòng 1: giá trị trả về của max_score

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.