Cạnh lớn nhất

Trong một khu rừng già FPTOJ có \(N\) cái cây cổ thụ, giữa chúng được nối với nhau bởi \(N-1\) sợi dây leo. Mỗi sợi dây leo có một độ bền nhất định (là số nguyên dương). Một nhà thám hiểm muốn đi từ cây u sang cây \(v\) bằng cách bám vào các sợi dây leo. Anh ta chỉ có thể mang theo một lượng hành lý nhất định, và lượng hành lý tối đa mà anh ta có thể mang khi đi qua một tuyến đường bằng độ bền nhỏ nhất của các sợi dây trên tuyến đường đó. Với mỗi hành trình, hãy giúp nhà thám hiểm biết sợi dây yếu nhất (có độ bền nhỏ nhất) trên đường đi là bao nhiêu.

Yêu cầu: Cho \(N\) cây và \(N-1\) sợi dây leo. Trả lời Q truy vấn, mỗi truy vấn yêu cầu in ra giá trị nhỏ nhất của các cạnh 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 cho biết sợi dây nối cây u và cây v có độ bền \(w\).
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng sau, mỗi dòng gồm hai số u, \(v\) là truy vấn.

Kết quả:

• In ra \(Q\) dòng, mỗi dòng là giá trị nhỏ nhất của các cạnh 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
4 5
1 4

Kết quả:

2
2
2

Giải thích:

• Đường đi \(4 \to 2 \to 1 \to 3\) có các cạnh \(\{2, 3, 5\}\), sợi yếu nhất là \(2\).
• Đường đi \(4 \to 2 \to 5\) có các cạnh \(\{2, 7\}\), sợi yếu nhất là \(2\).
• Đường đi \(1 \to 2 \to 4\) có các cạnh \(\{3, 2\}\), sợi yếu nhất 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 100000\) | \(Q \le 100000\) | 15 | | 7 | \(N \le 100000\) | \(Q \le 100000\) | 20 | | 8 | \(N \le 100000\) | \(Q \le 100000\) | 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\) (\(1 \le u, v \le N, 1 \le w \le 10^9\)).
• 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 2 số nguyên \(u, v\).

Định dạng đầu ra

• In ra trọng số cạnh lớn nhất trên đường đi từ \(u\) đến \(v\) cho mỗi truy vấn.

Ví dụ

Input:

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

Output:

8
8

Giải thích: Đường đi 1->3 gồm các cạnh 5 và 8 -> max là 8. Đường đi 3->4 gồm 8 và 3 -> max là 8.

Ràng buộc & Subtasks