题解

思路推导

把树根定为城市 $1$，记城市 $u$ 的深度为 $dep_u$，子树大小为 $siz_u$。若把 $u$ 选为工业城市，它自身到根的路径最多贡献 $dep_u$；另一方面，若 $u$ 保持工业属性，它不能作为旅游城市给子树内其他使者贡献幸福值，对应损失 $siz_u-1$。定义权值 $w_u=dep_u-(siz_u-1)$。

最优方案可以调整成“若某城市是工业城市，则它的工业后代优先于它被选择”的形态：若存在工业祖先和旅游后代，交换二者不会降低幸福值。沿父子边向下时，$w$ 严格增大，因此按 $w$ 从大到小选择恰好 $k$ 个城市，所得集合自动满足这一形态。

在这种集合中，不存在工业祖先和旅游后代。每个工业城市的深度贡献扣除其全部工业后代造成的旅游损失后，恰为 $w_u$。所以总幸福值就是所选城市权值之和。

做法

用一次树遍历求出每个城市的深度、父亲和遍历顺序，再逆序累加子树大小。计算所有 $w_u$，降序排序后取前 $k$ 个求和。

正确性证明

若一个方案中存在工业祖先 $u$ 和旅游后代 $v$，选择离 $u$ 最近的这类后代并交换二者，可以把工业城市向下移动。新工业城市路径不会更短，同时原工业祖先变成旅游城市，会补偿经过它的使者，故幸福值不减。重复交换可得到工业集合向叶端闭合的最优方案。

对任意父子关系，子城市的深度比父城市大一，而其子树严格包含于父城市子树，因此子城市的 $w$ 严格大于父城市的 $w$。所以取最大的 $k$ 个 $w$ 会得到一个向叶端闭合的集合。

在该集合中，每个工业城市先贡献其深度；每一对工业祖先与工业后代使后代路径少经过一个旅游城市。向叶端闭合保证某工业城市的所有后代均为工业城市，故它造成的扣减正好是 $siz_u-1$。总幸福值等于所选 $w_u$ 之和，算法选择其最大可能值，因此最优。

复杂度分析

树遍历为 $O(n)$，排序为 $O(n\log n)$，空间复杂度为 $O(n)$。