| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P144PROA - ROUND 4A - Tổ dế mèn |
Dế mèn là loài côn trùng sống trong hang dưới lòng đất, và chúng có thói quen đào các đường hầm thông với nhau.
Dế cụ sống trong hang to nhất, gọi là ngôi nhà số 0. Các con dế khác, con, cháu, chắt, chít, anh chị em (đánh số từ 1 tới N-1) ... sống trong các ngôi nhà ở vùng lân cận. Mỗi con dế này tự đào 1 đường hầm dẫn tới mỗi ngôi nhà khác, và nó chỉ biết mỗi độ dài của đoạn đường này. Chúng muốn biết độ dài quãng đường tới ngôi nhà của các chú dế khác là bao nhiêu?
Các bạn hãy giúp lũ dế mèn thực hiện điều này.
Input
Gồm nhiều bộ test.
Mỗi bộ test gồm dòng đầu tiên là số nguyên N (2 <= N <= 10^5) là số chú dế mèn. N-1 dòng tiếp theo, mỗi dòng biểu đường hầm giữa 2 nhà. Dòng thứ i (1 <= i <= N-1) gồm 2 số nguyên A_i và L_i (L_i <= 10^9), thể hiện đường hầm giữa nhà dế mèn i và nhà dế mèn A_i, có độ dài là L_i.
Dòng tiếp theo là số nguyên Q (1<= Q <= 10^5) là số yêu cầu cần thực hiện.
Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên u_i, v_i, yêu cầu bạn tính độ dài đường đi ngắn nhất từ nhà dế mèn u_i tới v_i.
Input kết thúc bởi một số 0.
Output
Với mỗi test, in ra trên một dòng Q số nguyên, mỗi số là độ dài đường đi ngắn nhất giữa các cặp ngôi nhà của 2 chú dế theo yêu cầu đã cho.
Example
Input: 6
0 8
1 7
1 9
0 3
4 2
4
2 3
5 2
1 4
0 3
2
0 1
2
1 0
0 1
6
0 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
1
5 0
0 Output: 16 20 11 17
1 1
5000000000
Hình vẽ minh họa test 1:
| Được gửi lên bởi: | adm |
| Ngày: | 2014-02-26 |
| Thời gian chạy: | 3s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
