[CF1696F] Tree Recovery 题解

老莽莽穿一切 · 2022-07-01 18:47:49 · 题解

更好的阅读体验

考场一直在想神仙构造方法，实际上连最浅显的结论都没有发现。

首先关注到数据规模不大，想到通过某种方法构造完一棵树后暴力 \mathcal O\left(n^3\right) 判断是否满足要求的可行性。

这题还是比较需要思想火花的，如果想不到第一步的话根本做不下去，我们可以首先发现一个结论，就是如果确定一条边存在的话，假设这条边为 \langle x,y\rangle，因为这条边的存在，我们已经得知 \operatorname{dist}(x,y)=1，则如果存在 a_{x,z,y}=1，则说明 \operatorname{dist}(y,z)=\operatorname{dist}(x,y)=1，说明边 \langle y,z\rangle 也是存在的，以此类推我们可以得知图中所有的边。

其次，我们发现满足要求的树应当是唯一的，如果存在多种构造方案，即有一条边在某种方案中存在，在另一种方案中不存在，将这条边放在它不存在的方案中将形成一个环，这个环上任意相邻的两条边 \langle x,y\rangle,\langle y,z\rangle 都满足 a_{x,z,y}=1，则任意删去一条边都会导致存在一个不满足的条件。

那么我们现在就是要找到一条在最终答案中存在的边，因为数据规模不大，所以我们可以直接暴力枚举一条以 1 为端点的边，因为总有一条端点为 1 的边是被包含到答案里的，所以直接枚举构造，最后判断答案是否满足要求，时间复杂度 \mathcal O\left(n^4\right)，实际上因为跑不满所以很快，代码实现不难。