维护链信息
这些问题只需考虑在 $Splay$ 上如何维护就行,放几道例题
动态维护森林的连通性问题
板子里 $link$ 函数内部判断过此问题
维护边权
一般 lct 可以做到的是维护点权,而无法维护边权,一般的处理方法是将边也看做一个点即可。
维护生成树
一般问题是求一张无向图上求两点之间路径最大边权的最小值,同时可以加边。
由经典题目货车运输得出要动态维护一个最小生成树。
随手证明一下就知道,将新边 $(u,v)$ 加入生成树,并从树的环上删除一条边权最大的边。
所以 $Splay$ 维护的是最大点权。