主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
[CF1696F] Tree Recovery 题解
最后更新于 2025-07-31 11:16:53
作者
老莽莽穿一切
分类
题解
题解
CF1696F
复制 Markdown
查看原文
删除文章
更新内容
[更好的阅读体验](https://www.cnblogs.com/LaoMang-no-blog/p/16427416.html) --- 考场一直在想神仙构造方法，实际上连最浅显的结论都没有发现。 首先关注到数据规模不大，想到通过某种方法构造完一棵树后暴力 $\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)$，实际上因为跑不满所以很快，[**代码**](https://codeforces.com/contest/1696/submission/162387377)实现不难。
正在渲染内容...
点赞
10
收藏
0
