| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P132SUMC - SUM2 C - Mạng lưới giao thông |
Tại đất nước Highland, có N thành phố được nối với nhau bởi N-1 con đường hai chiều. Chiều dài của mỗi con đường đúng bằng 1 km. Mạng lưới giao thông luôn đảm bảo rằng khi bạn xuất phát từ một thành phố, bạn có thể đi tới các thành phố bất kì khác.
Kinh tế năm qua phát triển rất nhiều, vì vậy nhà vua đã quyết định đầu tư thêm cho hệ thống giao thông của đất nước. Để giảm chi phí đi lại cho người dân cũng như hoạt động các hoạt động kinh tế, nhà vua quyết định mở thêm một tuyến đường giữa hai thành phố, sao cho độ ổn định của hệ thống giao thông là nhỏ nhất. Độ ổn định của hệ thống giao thông được tính bằng tất cả các tổng đường đi ngắn nhất giữa các cặp thành phố (có tất cả N*(N-1)/2 cặp thành phố).
Nhiệm vụ của các bạn là hãy giúp nhà vua tìm độ ổn định nhỏ nhất cho hệ thống giao thông của đất nước?
Input
Dòng đầu tiên là số lượng các bộ test T (T <= 20).
Với mỗi test, dòng thứ nhất chứa số nguyên N là số thành phố của đất nước (N <= 300).
N-1 dòng tiếp theo, mỗi dòng chứa hai số u, v biểu diễn con đường nối giữa thành phố u và v.
Output
Với mỗi test, hãy in ra độ ổn định nhỏ nhất của hệ thống giao thông.
Example
Input:
1
3
1 2
2 3 Output:
3
Giải thích: con đường mới nối thành phố 1 với thành phố 3.
Khi đó độ ổn định của hệ thống giao thông sẽ giảm từ 4 xuống còn 3.
| Được gửi lên bởi: | adm |
| Ngày: | 2013-07-19 |
| 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 |
