【BZOJ2594】【WC2006】水管局长数据加强版

第一次写LCT好兴奋啊

因为之前连换根都不会(其他的东西也忘光了)

重新梳理一下LCT吧

LCT是通过将树剖分为链然后通过Splay维护链上信息的数据结构

由于链的划分方式,实现上一条链上点的深度为连续的一段,(我)习惯以越靠右的点深度越大

\(Access\)操作是把某个点到根节点的点变为一条独立的重链,实现方式为每次将当前点转到其所在Splay的顶端,然后将上一个点接到该点在Splay上的右侧(原来的右孩子断掉),再跳到父亲节点,直到做到树根为止。由于是用Splay维护的,

\(Makeroot\)操作即换根操作,将某个点\(Access\)后\(Splay\),此时该点所在Splay为它的所有父辈节点,此时只要翻转这个Splay,即翻转这一条链上的深度相对顺序,即可实现换根。

\(Link\)操作是把两个本来在不同树中的点连在一起。显然只需要将其中一个换为根接到另一个的上面即可。

\(Cut\)操作是把两个有边的点断开连接。把其中一个换为根,那么另一个一定是它的儿子(但在Splay中不一定是)。\(Access\)并\(Splay\)后断开即可。

\(Query\)操作即询问树上两点之间的信息,把一个换为根,\(Access\)另一个,那么得到的Splay上的值就是询问的值。

本题只要将操作倒序,不断加边即可,每次询问加边的两点之间边权最大的边并判断是否替换。

说点什么

您将是第一位评论人!

提醒
wpDiscuz