哇,做梦也没想到我居然能写LCT
题意:
给定n个点以及每个点的权值,要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。
0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。
1:后接两个整数(x,y),代表连接x到y,若x到y已经联通则无需连接。
2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。
3:后接两个整数(x,y),代表将点x上的权值变成y。
LCT(link cut tree)解决树上动态问题
1、查询、修改链上信息(min,max,sum,xor。。。。。。)
2、换根
3、动态连边,删边
4、合并两棵树
5、动态维护联通性
概念
虚边:连接儿子与父亲,儿子记录父亲,父亲不记录儿子(父不认子)
实边:父子互认,互相记录
每棵树维护多棵splay!!!(常数大。。。QAQ)
性质
1、每一个splay维护从上到下按在原树中的深度
严格递增的路径,且中序遍历splay得到的每个点的深度序列
****严格递增****
2、每个节点包含且仅包含与一个splay中
3、实边在splay中,
由一棵splay指向另一节点的边为虚边
(另一节点:该splay中中序遍历最靠前的点在原树中的父亲)

绿框中的为一个splay
里面都是实边
连接两个splay的是虚边
虚边中父亲不认孩子(透彻!!!)
4、某个点有多个儿子,只能认一个儿子拉入splay中
其它不行!(splay深度严格递增)
其它儿子父亲不认(虚边)
由儿子所属的splay的根的父节点指向该点,且父不认子。。。
神操作!
1、access(基础)
作用:打通根到某一节点的实链,放在同一splay中,且此节点的深度最深!
方式:虚边变实边,然后为了维护性质,原来实边变为虚边
由根到此节点的路径上全为实边
而且由于它是最深的,他下面都是虚的!!

没错就是这样!
实现:

