x. Link-Cut Tree

A forest under link and cut with path aggregates, path updates, rerooting, LCA and subtree sizes, each in $O(\log n)$ amortized (Sleator–Tarjan). The tree is split into preferred paths, each stored in a splay tree ordered by depth; a splay root’s parent pointer is a one-way path-parent pointer to the vertex its path hangs from. Everything reduces to access(v): make the root-to-$v$ path preferred, with $v$ at its bottom and at the root of its splay tree.

Check first whether something simpler fits:

Situation	Better tool
tree is static, path queries + updates	HLD — simpler, worst-case $O({\log }^{2}n)$
only subtree queries under link/cut	Euler Tour Tree — simpler
only connectivity, edges added and removed	segment tree on time + rollback DSU (offline)
only connectivity, edges only ever added	plain DSU
everything is offline	almost always something simpler than a link-cut tree
online link/cut and path aggregates	link-cut tree — this row is genuinely narrow
non-path (subtree, non-local) info under link/cut	Top Tree — the full generalisation, substantially harder, essentially never needed in a contest

Before writing 200 lines of link-cut tree, spend five minutes checking whether the problem is actually offline.

struct LinkCut {                                          // vertices 0..n-1; values on vertices
    struct Node { int ch[2]{0, 0}, p = 0, cnt = 1, tot = 1, vir = 0; ll val = 0, sum = 0, mx = LLONG_MIN, lz = 0; bool rev = false; };
    vector<Node> t;                                       // index 0 is the null node; vertex v is node v + 1
    LinkCut(int n) : t(n + 1) { t[0].cnt = t[0].tot = 0; for (int i = 1; i <= n; i++) t[i].mx = 0; }
    bool isRoot(int x) const { int p = t[x].p; return !p || (t[p].ch[0] != x && t[p].ch[1] != x); }
    void pull(int x) {
        auto &a = t[t[x].ch[0]], &b = t[t[x].ch[1]];
        t[x].cnt = a.cnt + b.cnt + 1; t[x].tot = a.tot + b.tot + 1 + t[x].vir;
        t[x].sum = a.sum + b.sum + t[x].val; t[x].mx = max({a.mx, b.mx, t[x].val});
    }
    void addAll(int x, ll v) { if (!x) return; t[x].val += v, t[x].sum += v * t[x].cnt, t[x].mx += v, t[x].lz += v; }
    void flip(int x) { if (!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev ^= 1; }
    void push(int x) {
        if (t[x].rev) flip(t[x].ch[0]), flip(t[x].ch[1]), t[x].rev = false;
        if (t[x].lz) addAll(t[x].ch[0], t[x].lz), addAll(t[x].ch[1], t[x].lz), t[x].lz = 0;
    }
    void rotate(int x) {
        int p = t[x].p, g = t[p].p, d = t[p].ch[1] == x;
        if (!isRoot(p)) t[g].ch[t[g].ch[1] == p] = x;
        t[x].p = g; t[p].ch[d] = t[x].ch[!d]; if (t[x].ch[!d]) t[t[x].ch[!d]].p = p;
        t[x].ch[!d] = p; t[p].p = x; pull(p); pull(x);
    }
    void splay(int x) {
        static vector<int> st; st.clear();
        for (int y = x;; y = t[y].p) { st.push_back(y); if (isRoot(y)) break; }
        while (sz(st)) push(st.back()), st.pop_back();
        while (!isRoot(x)) {
            int p = t[x].p;
            if (!isRoot(p)) rotate((t[p].ch[1] == x) == (t[t[p].p].ch[1] == p) ? p : x);
            rotate(x);
        }
    }
    int access(int x) {                                   // returns the last path-parent jumped to (gives the LCA)
        int last = 0;
        for (int y = x; y; y = t[y].p) {
            splay(y); t[y].vir += t[t[y].ch[1]].tot - t[last].tot;   // old preferred child becomes virtual
            t[y].ch[1] = last; pull(y); last = y;
        }
        splay(x); return last;
    }
    void makeRoot(int x) { access(x); flip(x); }
    int findRoot(int x) { access(x); while (t[x].ch[0]) push(x), x = t[x].ch[0]; splay(x); return x; }
    // ---- public API, 0-indexed ----
    bool connected(int u, int v) { return findRoot(u + 1) == findRoot(v + 1); }
    bool link(int u, int v) {                             // add edge u - v (false if already connected)
        u++, v++; makeRoot(u); if (findRoot(v) == u) return false;
        access(v); t[u].p = v; t[v].vir += t[u].tot; pull(v); return true;
    }
    bool cut(int u, int v) {                              // remove edge u - v (false if absent)
        u++, v++; makeRoot(u); access(v);
        if (t[v].ch[0] != u || t[u].ch[1]) return false;
        t[v].ch[0] = t[u].p = 0; pull(v); return true;
    }
    void setVal(int v, ll x) { v++; access(v); t[v].val = x; pull(v); }
    void pathAdd(int u, int v, ll x) { u++, v++; makeRoot(u); access(v); addAll(v, x); }
    ll pathSum(int u, int v) { u++, v++; makeRoot(u); access(v); return t[v].sum; }
    ll pathMax(int u, int v) { u++, v++; makeRoot(u); access(v); return t[v].mx; }
    int lca(int u, int v, int root) { makeRoot(root + 1); access(u + 1); return access(v + 1) - 1; }   // same tree
    int subtreeSize(int v, int root) { makeRoot(root + 1); access(v + 1); return t[v + 1].vir + 1; }
};

Detail	Why
isRoot	a node’s parent is either its splay parent or a path-parent; it is a splay root iff the parent does not list it as a child
push before splaying	collect the splay ancestors and push top-down, else rotations mix unpushed reversals
vir	total size of the subtrees hanging off a node through path-parent pointers; makes subtree sizes (and, with a parallel vsum, subtree sums) available after access
edge values	create a node per edge, link u - e - v, give vertices a neutral value
non-commutative path aggregates	store both directions and swap them in flip
subtree aggregates beyond size	hard: link-cut trees natively handle paths; a full subtree sum/min/max needs the virtual-subtree augmentation above (tracking an aggregate of every virtually-hanging subtree, updated in access/link/cut) — it roughly doubles the code, so prefer an Euler Tour Tree if subtree-only queries suffice

Proof: correctness of access and the derived operations

Representation invariant: each splay tree stores one preferred path in depth order (in-order = top to bottom); the parent pointer of a splay root points to the parent (in the real tree) of the top of its path. access(x): after splay(y), the right subtree of $y$ holds the part of $y$‘s path below $y$; replacing it with the previously built tree last (the path from just below $y$ down to $x$) cuts the old lower part off (it keeps its path-parent pointer to $y$, now a virtual child) and splices the new part in. Repeating up to the root makes the root-to-$x$ path one splay tree; the final splay(x) puts $x$ at its root with nothing to its right (it is the deepest). makeRoot: after access(x) the splay tree is the root-to-$x$ path; reversing it makes $x$ the top, i.e. reroots the real tree at $x$ (all other paths hang off vertices and are unaffected). Path $u$–$v$: after makeRoot(u) and access(v), $v$‘s splay tree holds exactly the $u$–$v$ path, so its aggregate is the path aggregate and a lazy tag on it updates exactly the path. link / cut: after makeRoot(u), $u$ is a real root; giving it path-parent $v$ adds the edge. For cut, $u$–$v$ is an edge iff after access(v) the path is exactly $u,v$, i.e. $u$ is $v$‘s left child with no right child. LCA: after access(u), the second access(v) climbs from $v$; the last path-parent jump lands on the first vertex of the root-to-$u$ path met by $v$‘s root path, which is the LCA. Subtree size: after access(v) (rooted at root), $v$ has no preferred child, so its real subtree is $v$ plus everything hanging off it virtually: vir + 1; vir is maintained whenever a child switches between preferred and virtual (in access and link) and summed in pull.

Proof sketch: $O(\log n)$ amortized

Two parts. Preferred-child changes: call a tree edge $(p,c)$ heavy if $c$ holds more than half of $p$‘s subtree; each vertex has at most one heavy child edge and every root path has at most ${\log }_{2}n$ light edges. Each path-parent jump in access makes some edge preferred. Making a light edge preferred is charged to the access ($\le {\log }_{2}n$ per access). A heavy edge becomes non-preferred only when another child edge of the same parent, necessarily light, becomes preferred; so heavy edges become preferred at most (number of light-preferred events) $+(n-1)$ times. Link and cut change subtree sizes only on one root path and add $O(\log n)$ light-edge events each. Hence $O((n+m)\log n)$ jumps over $m$ operations. Splaying: with the potential ${\sum }_x\log ({\text{tot}}_x)$ over the virtual tree that includes path-parent links, the splay access lemma makes all the splays of one access telescope to $O(\log n)$ amortized plus $O(1)$ per jump. Combined: $O(\log n)$ amortized per operation.

Online minimum spanning forest

Represent each edge as its own node carrying the weight (vertices carry $-\infty$). Inserting $(u,v,w)$: if $u,v$ are disconnected, link through the edge node; otherwise find the heaviest edge on the tree path, and if it is heavier than $w$, cut it and link the new one.

struct OnlineMSF {                                        // insert-only minimum spanning forest
    int n; LinkCut lc; vector<array<ll, 3>> ed; ll total = 0;   // edge node i lives at index n + i
    OnlineMSF(int n, int maxEdges) : n(n), lc(n + maxEdges) { for (int v = 0; v < n; v++) lc.setVal(v, LLONG_MIN / 2); }
    int heaviest(int u, int v) {                          // edge-node index of the path maximum
        int x = u + 1; lc.makeRoot(x); lc.access(v + 1);
        for (ll m = lc.t[x = v + 1].mx;;) {               // descend in the splay tree towards the maximum
            lc.push(x);
            if (lc.t[x].val == m) break;
            x = lc.t[lc.t[x].ch[0]].mx == m ? lc.t[x].ch[0] : lc.t[x].ch[1];
        }
        lc.splay(x); return x - 1;
    }
    void insert(int u, int v, ll w) {
        if (u == v) return;
        int e = n + sz(ed); ed.push_back({u, v, w}); lc.setVal(e, w);
        if (!lc.connected(u, v)) { lc.link(u, e), lc.link(e, v); total += w; return; }
        int f = heaviest(u, v); if (lc.t[f + 1].val <= w) return;
        auto [a, b, wf] = ed[f - n]; lc.cut(a, f), lc.cut(f, b); total -= wf;
        lc.link(u, e), lc.link(e, v); total += w;
    }
};

Proof: the swap rule keeps a minimum spanning forest

Invariant: the stored forest is a minimum spanning forest of the edges inserted so far. A new edge between two components must be in every spanning forest of the new graph that is maximal, and adding it to an MSF of the old graph gives an MSF (any spanning forest of the new graph restricted to old edges spans the old components minus one merge, so it weighs at least the old MSF; adding the new edge is forced). If $u,v$ are connected, the new edge closes exactly one cycle with the forest; by the cycle property the heaviest edge of that cycle is not needed, so removing the heaviest of {path maximum, new edge} gives an MSF of the new graph: if the new edge is heavier, nothing changes; otherwise the path maximum leaves. The descent finds a node whose value equals the subtree maximum by following a child with the same mx.

Other applications

Dynamic trees were introduced by Sleator and Tarjan precisely to speed up network flow algorithms by pushing along a whole path in $O(\log n)$ instead of one edge at a time; Goldberg–Tarjan push-relabel with dynamic trees reaches $O(nm\log \frac{n^2}{m})$ — see Theoretical Algorithms Catalog. The same idea speeds up Dinic-style blocking flows.