[SDOI2008]Cave 洞穴勘测

[SDOI2008]Cave 洞穴勘测
此题又三个操作,连接x,y一边,摧毁x,y一边,问x,y是否联通。着就是动态树LCT裸题了,连接就link,摧毁就cut,询问联通就问x,y的根是否一样即可。

[SDOI2016]生成魔咒

[SDOI2016]生成魔咒
这题就是SAM后缀自动机的基本操作了。
对于当前新增节点x的操作,每次对ans的贡献就是dep[x]-dep[fail[x]],
x<=10^9怎么破,数组开不够大呢,那么我们就用map代替就好了呀