Python Program for Link-Cut Tree

Link-Cut Trees are advanced data structures used to dynamically maintain forests of trees with efficient updates and queries.

They support operations like linking two nodes, cutting edges, and querying paths in logarithmic time.

1. Understanding the Problem

Maintain a dynamic tree where edges can be added or removed, and queries can be performed on paths.

Operations: link(u, v), cut(u, v), find-root(u), path-query(u, v)

2. Method 1: Basic Concept

# Link-Cut Tree uses Splay Trees
# Each node represents a vertex
# Preferred paths are maintained dynamically
# Supports dynamic connectivity

The structure is based on splay trees and preferred path decomposition.

3. Method 2: Node Structure

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
        self.reversed = False

Each node stores pointers and lazy propagation flags.

4. Method 3: Splay Operation

def rotate(x):
    p = x.parent
    g = p.parent

    if p.left == x:
        p.left = x.right
        if x.right:
            x.right.parent = p
        x.right = p
    else:
        p.right = x.left
        if x.left:
            x.left.parent = p
        x.left = p

    p.parent = x
    x.parent = g


def splay(x):
    while x.parent:
        p = x.parent
        g = p.parent

        if g:
            if (g.left == p) == (p.left == x):
                rotate(p)
            else:
                rotate(x)
        rotate(x)

Splay operation brings a node to the root of its auxiliary tree.

5. Method 4: Access Operation

def access(x):
    last = None
    while x:
        splay(x)
        x.right = last
        last = x
        x = x.parent

Access operation exposes the path from node to root.

6. Method 5: Link and Cut

def link(u, v):
    access(u)
    u.parent = v


def cut(u):
    access(u)
    if u.left:
        u.left.parent = None
        u.left = None

These operations modify the tree dynamically.

7. Algorithm

1. Represent tree using splay trees.

2. Use access() to expose paths.

3. Perform rotations to maintain structure.

4. Use link() and cut() for updates.

5. Query paths using exposed trees.

8. Common Mistakes

1. Incorrect splay rotations.

2. Forgetting parent updates.

3. Mishandling lazy propagation.

4. Debugging complexity issues.

9. Applications

1. Dynamic connectivity problems.

2. Network optimization.

3. Advanced graph algorithms.

4. Competitive programming (rare but powerful).

Conclusion

Link-Cut Trees are among the most advanced data structures in computer science.

They allow efficient dynamic tree operations that are otherwise very difficult to implement.