Cạnh nhỏ nhất

Vương quốc FPTOJ có \(N\) thành phố được kết nối với nhau bởi \(N-1\) con đường, tạo thành một mạng lưới liên thông. Mỗi con đường có một độ khó đi qua (là một số nguyên dương). Hoàng tử của vương quốc muốn đi thăm các thành phố, nhưng chàng chỉ muốn đi qua những con đường dễ đi nhất có thể. Với mỗi hành trình từ thành phố u đến thành phố \(v\), chàng muốn biết con đường dễ đi nhất (có độ khó nhỏ nhất) trên đường đi là bao nhiêu.

Yêu cầu: Cho \(N\) thành phố và \(N-1\) con đường. Trả lời Q truy vấn, mỗi truy vấn yêu cầu in ra giá trị nhỏ nhất trong 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 có con đường nối hai thành phố u và v với độ khó \(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\}\), giá trị nhỏ nhất là \(2\).
• Đường đi \(4 \to 2 \to 5\) có các cạnh \(\{2, 7\}\), giá trị nhỏ nhất là \(2\).
• Đường đi \(1 \to 2 \to 4\) có các cạnh \(\{3, 2\}\), giá trị nhỏ 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 nhỏ 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:

5
3

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

Ràng buộc & Subtasks