警示后人,会wa第十个点的原因
查看原帖
警示后人,会wa第十个点的原因
578590
Inui_Sana楼主2022/7/16 15:20

应该wa了第十个点的人看了题解或讨论都知道,判断条件要写dfn[v]<=dfn[b]而不是dfn[u]<dfn[b]

那这是为什么呢?我们可以来看一下这一组数据:

7
5 1
1 2
2 6
2 3
3 4
4 5
6 7
0 0
1 3

建出来的图是这样的:

然而我们会发现,写前者跑出来的正解是 No solution,而后者却跑出来了 22。这是因为在从 2266 这课子树时,dfnudfn_u 已经处理出来是 22,而 dfnbdfn_b33,会错误地判断出“22 阻断了 1133 之间的道路”这一结论,而严格地搜索子树 vv 则不会出错。

见到很多题解没有解释该写法错误的原因,故发此帖,顺便提供一组小 hack 数据。

ps:若用邻接表,可以将数据中的 5 12 6放到后面,主要是为了先搜到 33 再搜到 66

2022/7/16 15:20
加载中...