挑战竞选CSP-S T2最复杂做法，心态爆炸求助

首先跑一个最小生成树，然后枚举要城镇化的乡镇，设当前要城镇化的乡镇编号为 $k$，发现一个城镇化的乡镇必定要连接 $a_{k,x}$ 最小的城市（调整法可证），然后以这个城市作为树根进行树形DP，$f_{i,1}$ 表示以 $i$ 为根的连通子树内有连接第 $k$ 个城镇化的乡镇的节点，$f_{i,0}$ 表示以 $i$ 为根的连通子树内没有连接第 $k$ 个城镇化的乡镇的节点，转移时 $f_{i,1}$ 转移到 $f_{i,0}$ 可以断一条边，$f_{i,0}$ 转移到 $f_{i,1}$ 需要 $a_{k,i}$ 的代价，计算最小代价，然后发现树的形态已经不对了，需要找出所有连接第 $k$ 个城镇化的乡镇的节点连接到树根，然后把刚才没断掉的边取出来再建一棵树，复杂度$O(n 2^k+m\log m)$，场上写了3h，考完破防了

挑战竞选CSP-S T2最复杂做法，心态爆炸求助