Lubenica

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.88s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Croatian OI 2006
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mạng lưới giao thông ở ~1~ nước bao gồm ~N~ thành phố (đánh số từ ~1~ đến ~N~) và ~N-1~ đường nối các thành phố với nhau. Có một đường đi duy nhất giữa mỗi cặp thành phố. Mỗi con đường có một độ dài xác định.

Viết chương trình, với mỗi ~K~ cặp thành phố cho trước, tìm độ dài của con đường ngắn nhất và dài nhất trên đường đi giữa ~2~ thành phố này.

Input

Dòng đầu tiên chứa số nguyên ~N~, ~2 \leq N \leq 100000~.

Mỗi dòng trong số ~N-1~ dòng tiếp theo chứa ~3~ số nguyên ~A~, ~B~, ~C~ cho biết có một con đường độ dài ~C~ giữa thành phố ~A~ và thành phố ~B~. Độ dài của mỗi con đường là số nguyên dương không vượt quá ~1000000~.

Dòng tiếp theo chứa số nguyên ~K~, ~1 \leq K \leq 100000~.

Mỗi dòng trong số ~K~ dòng tiếp theo chứa ~2~ số nguyên ~D~ và ~E~ - chỉ số của ~2~ thành phố cần truy vấn ~(D \neq E)~.

Output

Mỗi dòng trong số ~K~ dòng chứa ~2~ số nguyên - độ dài của con đường ngắn nhất và dài nhất trên đường nối giữa ~2~ thành phố tương ứng.

Sample Input

5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2

Sample Output

100 200
50 150
50 100

Comments

Please read the guidelines before commenting.



  • 8
    leduykhongngu   commented on Jan. 3, 2022, 4:41 p.m.

    Đề bài đã được chỉnh sửa ~(D \neq E)~


  • 7
    6aren   commented on Jan. 3, 2022, 4:39 p.m.

    Đề nên nói rõ là ~D~ và ~E~ ở các truy vấn là phân việt