支配树

· · 个人记录

P2597（DAG支配树模板）

P8276（有向图支配树）

P9052（有向图支配树）

其中后两题有向图的支配关系为若干个基环树，可以通过 P7323 的 trick 缩所有只剩一个出边的点，剩余的点集为所有基环树的环上某一点，并且代表的树的点集两两不交，可以使用并查集维护信息。