[Solution] APC001E Antennas on Tree

cherry2010 · 2025-07-04 17:05:09 · 题解

考场做法，较为复杂。

我们记选择的点为关键点，合法情况为子树内所有点的坐标不同。

考虑一个子树中的情况，设子树根节点为 x，子节点个数为 son_x。对 son_x 分类讨论：

我们先按照这种方法统计出一个方案。

但这其实是有漏洞的。对于第二种情况，如果存在 fa_x 则可能出现下方的情况：即剩余 y_2 子树中没有标记，y_2 和 fa_x 的坐标相同。

但我们可以通过手动调整使 x 子树合法。容易发现，在整棵树上任意 x 子树外的关键点都可以使两者坐标不同。而这种情况只会在有 fa_x 时出现，也就是说根节点 rt 没有这种忧虑。那么如果 rt 是关键点，对其他所有点都一定会有“子树外的关键点”。所以只需要判断 rt 不是关键点时是否存在上方的不合法情况即可。

我们可以在统计方案时，对所有满足“有父节点且存在子节点的子树中没有关键点”的 x 打上标记。然后在方案统计结束后，统计每颗子树外的关键点数量。如果存在“有标记且子树外没有关键点”的点，rt 为关键点。

实现还是很简单的。

可能会有的疑惑：

• 整棵树为链怎么处理？

  • 直接将答案对 1 取 \max 即可。

• 在 son_x>1 的情况中，如果存在多个子树原本没有关键点，那么会留下一个子树的关键点数保持为 0，剩下的全部补为 1。但是留下的子树的选择会对答案产生影响吗？

  • 不会。首先对统计方案的计算是显然没有影响的。而对 rt 的选择判断，考虑分类讨论。
  • 如果 x 不为根，此时 x 上是有标记的。如果 x 外没有关键点，那么 rt 会因为 x 的原因变为关键点。而如果 x 外有关键点，这些关键点也属于 x 子树外，所以 x 子树内的标记不会影响到 rt。
  • 如果 x 为根，那么原本没有关键点的子树一定都形如一条链，也就是都满足第一种情况，不需要考虑。