Chọn K Đỉnh Khoảng Cách Lớn Nhất
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh và $N - 1$ cạnh có trọng số dương $w$, cùng một số nguyên $K$. Hãy chọn đúng $K$ đỉnh phân biệt sao cho tổng khoảng cách giữa tất cả $\binom{K}{2}$ cặp đỉnh được chọn là lớn nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
- $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$.
Dữ liệu ra
- Một số nguyên duy nhất là tổng khoảng cách cặp đỉnh lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 2 1 2 5 2 3 3 2 4 2 |
8 |
Giới hạn
- $1 \le K \le N \le 2000$
- $1 \le w \le 10^6$
Community Discussion