发现对于 $k=0$ 的情况，答案显然是 $2\times (n-1)$。

在一棵树上连一条边，显然会出现一个环，那么我们发现如果增加了一个环，换上的边就只会访问一次，那么显然答案就是 $2\times(n-1)-d+1$，其中 $d$ 是环的长度。显然我们可以贪心的选择直径，这样显然是最优的。

对于有 $2$ 个环的情况，显然我们发现重复的环会使重复的地方的会多访问一次，而没有在环上的点又会少访问一次。那么可以将树的直径的边权设为 $-1$，最后的答案相减就是答案了，时间复杂度为 $O(n)$。

收获：贪心的题目要先推测结论在进行证明。