Chọn K Đỉnh Khoảng Cách Lớn Nhất

Buổi 34 — Tree DP & Rerooting Dynamic Programming
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved