$\texttt{CF269D}$

建边部分几乎一样，只用把后面的最小生成树改成dp即可。