我们如果有一棵生成树，现在要往里面加入一个点 那么贪心的加边即可（枚举该点到生成树每一个点的连边） 当然上述做法显然有纰漏，如果这个点的最优路径端点不在生成树中，就不对了 但是如果给定一个加点序列，我们会发现上述贪心得出的是该排列下的最优解。 所以枚举全排列，之后贪心即可 那么仔细的看一下，其实贪心不仅是该选择排列下的最优解 还是深度序列下的最优解 我们枚举的全排列很多，但是对应的深度序列却很少 那么可不可以从深度开始思考呢？ 我们设 dpdpdp [ iii ][ jjj ]表示一个有集合 iii ，最大深度为 jjj 的生成树的代价之和 值为 0x3f3f3f3f0x3f3f3f3f0x3f3f3f3f 为不存在 （似乎还有一个保存最后一层的数组，但这其实是不必要的） 那么转移的时候，如果 iii ， jjj 存在 那么它的下一层可以是 iii 的补集的子集 也就是说要枚举 iii 的补集的子集，然后按刚才的贪心法则走 就能计算出下一个状态的值。 只是有一个问题，这样计算出的值显然偏大，并且永不偏小 因为我们把所有点的深度都按最大深度算了， 但是，我们可以证明，存在一些状态它们的值是准的 而问题的正解就在其中。你取 minminmin ，就可以滤掉错解 （好好想想，你要是每一层都恰好蒙对了，贪心出的路径就是上下两层之间的） 这样那个保存最后一层的数组就没有必要设了 另外有一个技巧， 设全集为 sss ，原集为 jjj 则 intintint k=sk=sk=s ^ jjj ; forforfor ( intintint i=ki=ki=k ; iii ; i=i=i= ( i−1i-1i−1 )& kkk ) 可以便利 jjj 补集的子集，同理如果把 kkk 换成 jjj 可以便利子集