Cạnh thứ K

Mạng lưới đường sắt của đất nước FPTOJ gồm \(N\) ga tàu được nối với nhau bởi \(N-1\) tuyến đường sắt. Mỗi tuyến đường có một chi phí bảo trì hàng năm (là số nguyên dương). Tổng công ty đường sắt muốn lên kế hoạch bảo trì cho từng tuyến đường. Với mỗi yêu cầu đi từ ga u đến ga v, họ muốn biết tuyến đường có chi phí bảo trì lớn thứ \(k\) trên đường đi đó là bao nhiêu, để ưu tiên bảo trì những tuyến đường đắt nhất trước.

Yêu cầu: Cho \(N\) ga tàu và \(N-1\) tuyến đường sắt. Trả lời Q truy vấn, mỗi truy vấn \((u, v, k)\) in ra chi phí lớn thứ k trên đường đi từ u đến \(v\).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(N\). - N-\(1\) dòng tiếp theo, mỗi dòng gồm ba số u, v, \(w\).
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng sau, mỗi dòng gồm ba số u, v, \(k\).

Kết quả:

• In ra \(Q\) dòng, mỗi dòng là chi phí lớn thứ \(k\) trên đường đi tương ứng.

Ví dụ:

Dữ liệu vào:

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

Kết quả:

2
3
2

Giải thích:

• Đường \(4 \to 2 \to 1 \to 3\): các cạnh \(\{2, 3, 5\}\) sắp xếp tăng dần \(\{2, 3, 5\}\), lớn thứ 1 là 2, lớn thứ 2 là \(3\).
• Đường \(4 \to 2 \to 5\): các cạnh \(\{2, 7\}\), lớn thứ 1 là \(2\).

Giới hạn: | Subtask | \(N\) | \(Q\) | Điểm | |---------|-----|-----|------| | 1 | \(N \le 100\) | \(Q \le 100\) | 5 | | 2 | \(N \le 500\) | \(Q \le 500\) | 5 | | 3 | \(N \le 2000\) | \(Q \le 2000\) | 10 | | 4 | \(N \le 10000\) | \(Q \le 10000\) | 10 | | 5 | \(N \le 50000\) | \(Q \le 50000\) | 15 | | 6 | \(N \le 50000\) | \(Q \le 50000\) | 15 | | 7 | \(N \le 50000\) | \(Q \le 50000\) | 20 | | 8 | \(N \le 50000\) | \(Q \le 50000\) | 20 |

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 3 số nguyên \(u, v, w\) mô tả một cạnh.
• Dòng tiếp theo: Số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo: mỗi dòng chứa 3 số nguyên \(u, v, K\) yêu cầu tìm trọng số cạnh thứ K trên đường đi từ u đến \(v\).

Định dạng đầu ra

• In ra trọng số của cạnh thứ \(K\) cho mỗi truy vấn.

Ví dụ

Input:

4
1 2 10
2 3 20
3 4 30
2
1 4 2
4 1 1

Output:

20
30

Giải thích: Đường đi 1->4 gồm các cạnh [10, 20, 30], cạnh thứ 2 là 20. Đường đi 4->1 gồm [30, 20, 10], cạnh thứ 1 là 30.

Ràng buộc & Subtasks