做法差不多想到了，缩无用点边也想到了，只是怎么 Kruskal 想挂了。。。

先把原图上无用边删掉，然后在加入所有新增边的基础上跑 Kruskal，缩掉所有不影响的边，从而压缩点、边集大小为 $O(k)$。

再 $O(2^k)$ 枚举加入边集，建出剩下边的 MST，再用被排开的边更新每条边边权上界，直接 dp 即可。

参考代码。