Những chấm tròn
Đề bài
Mô tả
Mika rất thích vẽ nguệch ngoạc vào vở. Hôm nay, cô vẽ chấm và nối chúng bằng đoạn thẳng. Các đoạn thẳng được vẽ sao cho cô có thể đi theo một đường từ một chấm bất kỳ tới một chấm bất kỳ khác mà không phải nhấc bút.
Các chấm được đánh số từ đến . Mika muốn đi theo một đường từ chấm tới một chấm nào đó mà không nhấc bút. Đường đi được phép đi qua một đoạn thẳng nhiều lần. Độ dài đường đi là số lần đi dọc theo một đoạn thẳng (mỗi lần đi qua một đoạn thẳng được tính một lần).
Để tăng thử thách, cô gán số nguyên cho các chấm. Với mọi chấm , cô phải đảm bảo đường đi của mình rời khỏi chấm đó không quá lần.
Với mỗi từ đến , hãy xác định độ dài lớn nhất của đường đi Mika có thể đi từ chấm tới chấm thỏa mãn các điều kiện trên.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên là số chấm ().
Dòng thứ hai chứa số nguyên (), trong đó là số lần nhiều nhất đường đi được rời khỏi chấm . Đảm bảo lớn hơn hoặc bằng số đoạn thẳng xuất phát từ chấm .
dòng tiếp theo, mỗi dòng chứa hai số nguyên và (), cho biết có một đoạn thẳng nối chấm và chấm .
Dữ liệu ra
Với mỗi từ đến , in ra một dòng chứa độ dài lớn nhất của đường đi kết thúc tại chấm .
Ràng buộc
- .
- , không nhỏ hơn số đoạn thẳng xuất phát từ chấm .
- Các đoạn thẳng tạo thành một cây (đi được giữa hai chấm bất kỳ).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 6 2 0 1 1 2 |
8 7 8 |
Kết thúc tại chấm : rời chấm hai lần, chấm bốn lần, chấm hai lần, độ dài . Kết thúc tại chấm : chấm chỉ được rời lần nên đoạn được đi tối đa lần, tổng . |
| 7 1 4 3 3 1 1 2 0 1 6 1 1 5 1 2 2 4 6 3 |
12 13 12 13 13 12 14 |
Đường đi phải liền mạch: muốn đi đoạn thì phải đi qua đoạn trước. Với chấm cuối là , mọi đoạn thẳng được đi đúng hai lần (mỗi chiều một lần), độ dài . |
Bình luận