社区讨论

警示后人,会wa第十个点的原因

P5058[ZJOI2004] 嗅探器参与者 9已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@lo8kd79l
此快照首次捕获于
2023/10/27 20:02
2 年前
此快照最后确认于
2023/10/27 20:02
2 年前
查看原帖
应该wa了第十个点的人看了题解或讨论都知道,判断条件要写dfn[v]<=dfn[b]而不是dfn[u]<dfn[b]
那这是为什么呢?我们可以来看一下这一组数据:
CPP
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

回复

8 条回复,欢迎继续交流。

正在加载回复...