【BZOJ2002】【HNOI2010】弹飞绵羊

嗯好我只是来学Link-cut tree的

好像说是动态树是一类问题 LCT是解决动态树的数据结构

随便怎么叫吧

然后我就来刷这道也可以说是动态树裸题的题了

所谓LCT。。似乎就是树链剖分+Splay

大概就是3个操作:

1.Access(x)

将x到根节点的路径全部改为重链(preferred line),取消该路径上所有点的其它重儿子(preferred child)(包括x的重儿子)

2.Cut(x)

断开x与其父亲的连接(把x所在子树移出)

3.Link(x,y)

将x所在子树接在y上

 

具体实现。。

。。

我不想讲了233

百度一堆233

那就发个代码吧233

这道题本来应该用分块写的。。

于是还是写了个分块

本地各种AC,提交上去又WA又TLE又RE(同时)

真是没戏了

求大神帮调

Subscribe
提醒
6 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments
4 年 之前

没戏

4 年 之前

彻底农烂

4 年 之前

彻底没戏

ZKB
4 年 之前

背起你的书包

LQB
4 年 之前

真垃圾

LQB
4 年 之前

来人农死你啊