函数图与构造 对每个顶点连边 ,得到每个顶点出度为一的函数图。每个弱连通分量恰好包含一个有向环,其余边构成指向环的树。
对于长度至少为三的环,删去任意一条边,将其余边作为朋友关系。长度为二的环表示两个人互相希望亲近,只保留一条无向边。舍弃自环,保留所有非环边。最后用任意边连接这些森林分量即可得到一棵树。
可以直接用并查集完成构造:依次处理 ,仅当两端属于不同集合时加入该边并合并。最后将顶点 与仍在其他集合中的顶点相连。
最优性证明 当 时该项始终为零;不在环上的非自身偏好至少贡献一。考虑长度为 的有向环。在任意最终树中,按环的顺序依次访问这些顶点并回到起点,把各段路径连接起来。连接这些顶点的最小子树中的每条边都至少被这条闭合路线经过两次。该子树包含 个不同顶点,至少有 条边,因此这个环对应的距离和至少为 。即使经过其他函数图分量中的顶点,这一下界也成立。
在上述构造中,长度 的环有 个偏好的距离为一,被删去的偏好距离为 ,总和恰为 。二元环的两个偏好距离均为一。所有非环偏好的距离也均为一。连接分量不会改变分量内部的唯一路径,因此同时达到全部下界。
最小值为:
用队列不断删除入度为零的顶点,剩下的恰好是环上顶点。遍历剩余各环并统计长度即可在 时间内计算公式。二元环虽然只使用一条朋友关系,但目标函数中两个偏好仍分别计数。
复杂度与验证 构造耗时 ,空间为 。图的深度可能达到 ,因此参考代码不使用递归 DFS。最优值在 到 之间。错误候选树的距离和可能高达 ,因此检查器使用有符号 位整数累加。顶点编号、度数和深度均不超过 。
检查器验证边数、端点及树结构,再用 LCA 计算实际距离和,与独立求出的最优值比较。其时间和空间复杂度均为 。
子任务 1 通过 Prüfer 序列枚举全部 棵带标号树。对每棵树从各顶点执行 BFS,可在 时间内计算目标值,总时间为 ,空间不超过 。 时足够。子任务 4 使用函数图与并查集。
Solution written by GPT6