P3690 【模板】Link Cut Tree (动态树)

 

哇,做梦也没想到我居然能写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中,且此节点的深度最深!

    方式:虚边变实边,然后为了维护性质,原来实边变为虚边

       由根到此节点的路径上全为实边

       而且由于它是最深的,他下面都是虚的!!

 

          没错就是这样!

实现:

 

复制代码
                        
关键字:
50000+
5万行代码练就真实本领
17年
创办于2008年老牌培训机构
1000+
合作企业
98%
就业率

联系我们

电话咨询

0532-85025005

扫码添加微信