关于虚树建树

P2495 [SDOI2011] 消耗战

理论上来说,这样做应该在最后一次之前都是没有问题的。 但是最后一次如果是 $dfn_{st[top - 1]}\neq dfn_{lca}$ 的话这样子做连边是有问题的,你应该连的边是 $st[top - 1] \rightarrow lca$ 和 $lca \rightarrow st[top]$,但是如果是和 $dfn_{st[top]}$ 比较的话会连出 $st[top - 1] \rightarrow st[top]$ 和 $st[top - 1] \rightarrow lca$。
by _LiMLE_ @ 2024-01-30 20:06:45


@[_LiMLE_](/user/480934) 好像知道了,谢谢大佬
by Isshiki·Iroha @ 2024-01-30 20:12:41


|