Tý cần giải bài toán sau:

Cạnh thứ K

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

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

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 | \(\le 100\) | \(\le 100\) | 5 | | 2 | \(\le 500\) | \(\le 500\) | 5 | | 3 | \(\le 2\)000\( | \)\le 2\(000\) | 10 | | 4 | \(\le 10\)000\( | \)\le 10\(000\) | 10 | | 5 | \(\le 50\)000\( | \)\le 50\(000\) | 15 | | 6 | \(\le 50\)000\( | \)\le 50\(000\) | 15 | | 7 | \(\le 50\)000\( | \)\le 50\(000\) | 20 | | 8 | \(\le 50\)000\( | \)\le 50\(000\) | 20 |