求助支配树(雾

P2597 [ZJOI2012] 灾难

@[Neutralized](/user/538609) 但是其实一般图支配树适用性更广然后也不难写,推荐去学一下。
by LingerFeng @ 2022-04-05 10:30:03


@[Myrrh](/user/698273) w,谢 教练给的网课讲了DAG支配树的求法 所以想先打下这个再去看一般图的 结果锅了(
by Neutralized @ 2022-04-05 10:31:56


@[Neutralized](/user/538609) 先提个醒,一般图支配树求法跟 DAG 支配树求法基本上一点关系没有,就算不学 DAG 支配树求法也一样可以学一般图的,反正时间复杂度差不多。
by LingerFeng @ 2022-04-05 10:34:51


问题出在求 `lst` 最近的一个支配点是 $\text{LCA}_{(u,v)}(v_i)$ 而不是 $\text{LCA}_{(u,v)}(lst_{v_i})$ 但是为什么源点取 `n+1` 会WA 90而取 `0` 就过了(
by Neutralized @ 2022-04-05 11:08:42


哦在[这](https://www.luogu.com.cn/discuss/326431) orz
by Neutralized @ 2022-04-05 11:13:24


|