CF1361E James and the Chase 题解

· · 题解

upd 2024/7/25：修改了部分 typo。

Description

给定一个有 n 个点 m 条边的有向强连通图。称一个点是好的当且仅当它到其他点都有且只有一条简单路径。如果好的点至少有 20\% 则输出所有好的点，否则输出 -1。

#### Solution 考虑给你一个点 $u$，如何判断其是否是好的。 那很简单是吧，只要以 $u$ 为根建出 `dfs` 树，没有**横叉边**或者**前向边**的话 $u$ 即为好节点。 那我们就可以 $O(n)$ 判断了。 如果我们现在知道一个点 $u$ 是好的，我们考虑如何求出所有的好节点。 还是以 $u$ 为根建出 `dfs tree`，考虑某个 $v$ 的子树，由于整个图的强连通性， $v$ 的子树中有连向其祖先的返祖边。我们不难发现这样的边有且仅有一条，否则 $v$ 有两条路径可以到达 $fa_v$ 即 $v$ 的父亲节点。 那我们先把所有子树 $v$ 内返祖到根的祖先的边的个数记下来，如果这个个数 $\ge 2$，排除 $v$ 是好点的可能，否则就顺便记下每个 $v$ 子树的那条返祖边指向的点。 假设 $v$ 的子树这条返祖边指向了 $w$，那么 $v$ 是好点，当且仅当 $w$ 是好点。考虑证明： - 如果 $w$ 是好点，那么 $w$ 到所有点路径唯一，又由于 $v$ 过 $w$ 出子树的路径是唯一的，所以 $v$ 到所有点的简单路径是唯一的，即 $v$ 是好点。 - 如果 $v$ 是好点，那么 $v$ 到所有点路径唯一，由于 $v$ 出子树必须要经过 $w$，所以 $w$ 到 $v$ 子树外所有点的路径也是唯一的，然后 $w$ 到 $v$ 的子树内的简单路径也是唯一的（没有前向边与横叉边），所以 $w$ 是好点。 所以综合所有的结论： 一个点 $v$ 是好点，当且仅当 $v$ 的子树内有且仅有一条连向 $v$ 的祖先的返祖边，并且这条边所连向的点是好点。 第一个条件可以考虑所有返祖边 $(a,b)$，它对哪些 $v$ 的子树内返向 $v$ 祖先的边的数量的有贡献。显然这样的 $v$ 分布在 $a\to fa_a\to...\to son_b$ 上，这里的 $son_b$ 为 $b$ 的儿子节点中靠近 $a$ 侧的那个，树上差分即可和第二个条件一起解决。 以上前提为 `dfs tree` 的根节点为好点。 那我们只要找到一个好点，并将其作为根节点，我们就能在 $O(n)$ 的范围内求解。 由于题目只要求好点数量大于等于 $20\%$ 时输出，所以我们随机取 $100$ 个点跑 $O(n)$ 判断。 如果好点数量不小于 $20\%$，你判断不出来的概率为 $\Big(\dfrac{4}{5}\Big)^{100}$ 趋近于 $0$。 所以随机跑 $100$ 次之后得不到一个好点的话就直接输出 $-1$，如果错了就是宇宙射线影响。 否则以找到的好点为根 $O(n)$ 求答案即可。 [评测链接。](https://codeforces.com/contest/1361/submission/179062861)