题解 P2147 【[SDOI2008]Cave 洞穴勘测】

· · 题解

题意:动态树+判断连通性

这道题我们当然可以用LCT做

但有一种更好的做法就是不路径压缩的并查集

link u,v:将u提根,然后设置u的父亲为v

cut u,v:将u提根,然后将v的父亲设为0

query u,v:u提根后直接暴力并查集查找v的祖先是不是u

提根:将u的父亲及其边全部反向

（看到没有并查集的题解过来水一发）