1. 题目
2. 题解
Link-Cut-Tree 的模板题啊……(听说还可以用其他的方法做,不管了,直接上 LCT)
没有要求维护点权,只需要维护点的连通性即可。
就是朴素的 LCT,居然还不要 pushup。
感觉有些不适应啊……. 不得不说 LCT 是个神器。
简单分析一下。
- 对于每种命令:
- 如果是
Connect x y (链接 x y)
: 直接link(x,y)
即可。 - 如果是
Destroy x y (切断 x y)
: 直接cut(x,y)
即可。 - 如果是
Query x y (询问 x y 的连通性)
: 判断findroot(x)
和findroot(y)
是否一致,一致输出Yes
,否则输出No
。
- 如果是
然后就 A 了。
0 条评论