「POI2011 R3」视察 Inspection 题解

问题简述

有一棵 $n$ 个节点的树，选定一个起点 $S$，要按以下规则访问所有其他节点：

每次从 $S$ 出发，去一个没访问过的节点 $v$，视察 $v$，然后返回 $S$

相邻两次出发必须走不同的边离开 $S$

访问完最后一个节点后不用回 $S$

每条边用时 1 小时

对每个可能的 $S$，求最小总时间，或输出 -1 表示不可能。

核心思路

1. 可行性判断 要能访问所有节点，必须满足：

从 $S$ 出发的每条边都至少用一次

总访问次数 = $n-1$ 次（除 $S$ 外的节点数）

这要求 $S$ 的度数 ≥ 2，且每个子树不能太大。

关键定理：只有当 $S$ 是树的重心时才可能。

2. 最小时间计算 总时间 = 所有往返时间之和 - 最后节省的时间

具体公式：

text 总时间 = 2 × 所有节点到S的距离之和 - 距离S最远的节点的距离 3. 高效算法 换根 DP 计算每个节点作为 $S$ 时的距离和

找重心 判断可行性

$O(n)$ 复杂度

算法步骤

第一遍 DFS：计算以 1 为根时每个节点的深度、子树大小

第二遍 DFS（换根）：计算每个节点作为根时的距离和

判断每个节点：

如果是重心且满足条件：按公式计算时间

否则：输出 -1

为什么这样对？ 距离和：总时间主要花在往返路上

减去最大距离：最后一次不用返回，省下最长的路

重心条件：保证能从不同边交替出发完成所有访问

这样就能在 $O(n)$ 时间内解决这个看起来复杂的问题。