## 正文

### 简介

link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations:

• Add a tree consisting of a single node to the forest.
• Given a node in one of the trees, disconnect it (and its subtree) from the tree of which it is part.
• Attach a node to another node as its child.
• Given a node, find the root of the tree to which it belongs. By doing this operation on two distinct nodes, one can check whether they belong to the same tree.

The represented forest may consist of very deep trees, so if we represent the forest as a plain collection of parent pointer trees, it might take us a long time to find the root of a given node. However, if we represent each tree in the forest as a link/cut tree, we can find which tree an element belongs to in O(log(n)) amortized time. Moreover, we can quickly adjust the collection of link/cut trees to changes in the represented forest. In particular, we can adjust it to merge (link) and split (cut) in O(log(n)) amortized time.

Link/cut trees divide each tree in the represented forest into vertex-disjoint paths, where each path is represented by an auxiliary data structure (often splay trees, though the original paper predates splay trees and thus uses biased binary search trees). The nodes in the auxiliary data structure are ordered by their depth in the corresponding represented tree. In one variation, Naive Partitioning, the paths are determined by the most recently accessed paths and nodes, similar to Tango Trees. In Partitioning by Size paths are determined by the heaviest child (child with the most children) of the given node. This gives a more complicated structure, but reduces the cost of the operations from amortized O(log n) to worst case O(log n). It has uses in solving a variety of network flow problems and to jive data sets.

In the original publication, Sleator and Tarjan referred to link/cut trees as “dynamic trees”, or “dynamic dyno trees”.

——Wikepedia

Link Cut Tree的基本操作复杂度均摊$O({\log}N)$，但常数较大，一般效率会低于树链剖分，但是却能解决许多树链剖分解决不了的问题。

### 性质

• 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。(就是)
• 每个节点包含且仅包含于一个Splay中，每一个父亲的向儿子的连边中有且只有一条边是实边
• 所有的实边包含在Splay中，而虚边总是指向另一个Splay中的某个节点(指向该Splay中中序遍历最靠前的点原树中的父亲)
• 所有的实边的父亲和儿子都要标记，虚边只要儿子记父亲(实边认父又认子，虚边认父不认子)

### 操作

#### access(x)

1-2-5-9变成实边

1. 转到根
2. 换儿子
3. 更新信息
4. 当前操作点切换为轻边所指的父亲，转1。

#### makeroot(x)

Splay上体现就是把整棵树反转一次

#### cut(x,y)

1. x和y在同一个原树
2. split后x是y的左儿子
3. x没有右儿子(保证了中序遍历中y紧跟在x的后面，即深度相邻)(x的权值(深度)只比y小1，而x又正好是直接连着y的，所以我们无法再找到 >x 而又 <y 的整数了)

## 发送评论编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)

Emoji