K đường đi
Đề bài
Mô tả
Trong lý thuyết đồ thị, cây là một đồ thị vô hướng liên thông và không có chu trình. Một cây có đỉnh có đúng cạnh. Với mọi cặp đỉnh trên cây, có đúng một đường đi đơn giữa và . Đường đi đơn là đường đi qua mỗi đỉnh không quá một lần.
Cho một cây gồm đỉnh, đánh số từ đến . Đỉnh thứ có nhãn .
Bạn cần chọn đường đi đơn rời nhau, sao cho đỉnh đầu của mỗi đường đi khác đỉnh cuối của nó, và giá trị lớn nhất của tổng nhãn hai đỉnh đầu mút của một đường đi là nhỏ nhất có thể.
Một cách hình thức, bạn cần chọn cặp đỉnh thỏa mãn tất cả các điều kiện sau:
- Với mọi thỏa mãn : .
- Xét đường đi đơn trên cây: đường đi đơn giữa và , đường đi đơn giữa và , ..., đường đi đơn giữa và . đường đi này phải đôi một rời nhau, nói cách khác, mỗi đỉnh của cây thuộc không quá một trong đường đi.
- Giá trị nhỏ nhất có thể.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (, ).
- Dòng thứ hai chứa số nguyên ().
- dòng cuối, mỗi dòng chứa hai số nguyên và () cho biết hai đỉnh và được nối trực tiếp bởi một cạnh.
Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây.
Dữ liệu ra
In ra một số nguyên là giá trị nhỏ nhất có thể của biểu thức trên. Nếu không thể chọn cặp đỉnh thỏa mãn tất cả các điều kiện trên, in ra .
Ràng buộc
- , .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 10 20 30 40 1 2 2 3 3 4 |
70 | Chọn hai đường đi (tổng ) và (tổng ). |
| 4 1 10 20 30 40 1 2 1 3 1 4 |
30 | Chọn đường đi với tổng . |
| 4 2 10 20 30 40 1 2 1 3 1 4 |
-1 | Mọi đường đi có ít nhất hai đỉnh đều đi qua đỉnh , nên không thể chọn hai đường đi rời nhau. |
Bình luận