splay tree

key idea. after each (insert/find/erase). make the vertex to root.

by rotation zig, zig-zag or zig-zig.

link cut tree(forest)

let's call LCT graph, splay tree. to avoid ambiguity

every prefered path(component, real edge, heavy path) is a splay tree by depth.(aka, in-order the splay tree, sorted by depth in graph). let's call it S. since it's a splay tree.

how each S. connected? by S's root -> S's smallest depth(in graph)(left-most in-order in tree)'s parent. called path parent pointer(ppp).

for short memorization, LCT definition

1. (prefered)path is S.
2. ppp: S.'s root -> S.'s left's parent

by store information in this way, allow us to do dynamic operation.

first, key part

access(v)

well, access actually does is making the path from graph's root to v be prefered.

by loop up S. splay(x), make their ppp real, till the graph's root. (this key short explantion, and rembember LCT'def)

in the end, we can splay(v) or not, depends.

link(u, v) or link(v)

link the two graph. there is option, the link could be prefered or not(light).

cut(u,v) or cut(v)

separate to two graph.

hint. keep in mind what access does.

useful links

http://web.stanford.edu/class/cs166/lectures/10/Small10.pdf

https://courses.csail.mit.edu/6.851/spring12/scribe/L19.pdf

https://www.cnblogs.com/flashhu/p/8324551.html

https://www.cnblogs.com/flashhu/p/9498517.html