官方题解

题目描述

Treeland 有 $n$ 个城市,标号从 $0…n-1$。有 $n-1$ 条双向道路连接了 $n$ 个城市构成一颗树。 Treeland 的居民想要建造一套 TPS 系统 (Treeland Positioning System)。TPS 是一个能帮助人定位他在哪个城市的系统。系统由 $k$ 个信标构成,每个信标被安放在一个城市。当一个人打开他的 TPS 接收器的时候他能得到他与每一个信标的距离 (这里距离指树上两点之间经过的边的数量) 。 显然只有当在不同的城市打开 TPS 接收器接受到的信息不一样的时候 TPS 系统才能正常工作。(也就不存在两个不同的城市使得在他们那里接收到的信号相同)注意不同的信标之间是可以区分的。求最少安放多少信标才能使 TPS 系统正常工作。

约定与限制

  • $n\in [1,50]$
  • 时间限制: $2$ s
  • 空间限制: $64$ MB

思路

我们先假定选择了一个点为根,并且在根节点放置了信标。

设一个节点有 $c$ 个儿子,发现必须在其中至少 $c − 1$ 个儿子的子树中放置信标。证明如下:

  • 考虑如果不这样放,对于两棵都没有放的子树,他们汇集到 $lca$ 上以后距离都是相等的,所以 $lca$ 外的信标无法区分,而内部没有信标。所以不能存在两颗子树都不放,至少要放 $c − 1$ 个;

  • 由于在根节点放置了信标,可以只考虑深度相同的点。因为他们的 $lca$ 度数至少为 2,那么一定有一个信标在 $lca$ 包含这两个点的两支子树中。那么另一侧的点肯定要走更远的路,会被区分开。所以放 $c − 1$ 个足够区分。

所以,对于一个确定的根,我们可以贪心地放置信标,得到当前的答案。

如何选择这个根呢?找到任意一个度数大于 2 的节点,可以证明实际上这个点一定不需要放置信标,以这个点作根 $\Theta(n)$ 的贪心即可。证明如下:

对于深度相同的点,显然两个信标就可以区分它们,现在只考虑深度不同的点对。如果它们在一颗子树中,由于度数大于 2 所以一定有另一颗子树的一个信标把他们区分开。如果在不同的子树中,有两种情况:

  • 一个在没放信标的子树中,一个在放了的子树中。显然还存在另一个子树放了信标,由于深度不同他们会被这个信标区分开。

  • 两个都在放了信标的子树中。如果根的度数大于 3 则另一个子树的信标会区分它们同上。度数等于 3 时,如果他们没有被区分开,一定是他们先汇集到了一个节点,然后走到同一个信标上。这个点一定是一条奇链的中点,且不是根 (由于深度不同),是在两个子树之一中唯一的。那么他们走到另一个信标就一定有一个点走了更远的路,既另一个信标可以区分出他们。

所以最后的时间复杂度 $\Theta(n)$。

代码