Link-Cut Tree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct LCT {
    struct Node {
        ll val, sz;
        int par, ch[2];
    };

    vector<Node> t;

    LCT(int n) : t(n + 1) {
        for (int i = 1; i <= n; i++)
            t[i] = {1, 1, 0, {0, 0}};
    }

    bool isRoot(int x) { return !t[x].par || (t[t[x].par].ch[0] != x && t[t[x].par].ch[1] != x); }
    bool isRight(int x) { return t[t[x].par].ch[1] == x; }
    void pull(int x) { t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + t[x].val; }

    void rotate(int x) {
        int p = t[x].par, g = t[p].par, d = isRight(x);
        if (!isRoot(p)) t[g].ch[isRight(p)] = x;
        t[p].ch[d] = t[x].ch[!d];
        if (t[p].ch[d]) t[t[p].ch[d]].par = p;
        t[x].ch[!d] = p;
        t[p].par = x; t[x].par = g;
        pull(p); pull(x);
    }

    void splay(int x) {
        while (!isRoot(x)) {
            int p = t[x].par;
            if (!isRoot(p)) rotate(isRight(p) == isRight(x) ? p : x);
            rotate(x);
        }
    }

    void expose(int x) {
        for (int p = 0; x; p = x, x = t[x].par) {
            splay(x);
            if (t[x].ch[1]) t[x].val += t[t[x].ch[1]].sz;
            if (p) t[x].val -= t[p].sz;
            t[x].ch[1] = p;
            pull(x);
        }
    }

    void makeRoot(int x) {
        expose(x); splay(x);
        t[x].val = -t[x].val;
        swap(t[x].ch[0], t[x].ch[1]);
    }

    int getRoot(int x) {
        expose(x); splay(x);
        while (t[x].ch[0]) x = t[x].ch[0];
        splay(x); return x;
    }

    bool connected(int x, int y) { return getRoot(x) == getRoot(y); }

    void link(int x, int y) {
        expose(x); splay(x);
        expose(y); splay(y);
        t[y].par = x; t[x].val += t[y].sz;
        pull(x);
    }

    void cut(int x, int y) {
        expose(y); splay(x);
        t[x].ch[1] = t[y].par = 0;
        pull(x);
    }

    ll query(int x, int y) {
        makeRoot(x); expose(y);
        return t[y].sz;
    }
};