题意

从前有棵树。找出 $K$ 个点 $A_1,A_2,\cdots,A_k$ ，使得 $\sum_{i=1}^{K-1}\mathrm{dis}(A_i,A_{i+1})$ 最小。

$1\leq k\le n,1\le x,y\le n,1\le z\le 10^5,n\le 3000$

口胡

两个结论：

1. $K$ 个点一定要缩在一起，即选出来的一定是恰好 $K$ 个点构成的子树。
2. 像毛毛虫那样，一条直径，然后每次从直径的某点出去再回来，即直径边只经过 1 次，非直径遍一定经过 2 次。

然后 DP 即可，设 $f_{i,j,0/1/2}$ 表示以 $i$ 为根的子树中选 $j$ 个点且直径的端点选了 0/1/2 个。

大概是 $\mathcal{O}(n^2)$ 的。