Link-Cut Tree

struct Node
{
    Node *left;
    Node *right;
    Node *parent;
    Node *link;
    int x;
    bool rev;
    Node(int x = 0):
        left(0),
        right(0),
        parent(0),
        link(0),
        x(x),
        rev(0){}

};

void push(Node *v)
{
    if (v == NULL || !v->rev)
        return;
    v->rev = 0;
    swap(v->left, v->right);
    if (v->left != NULL)
        v->left->rev ^= 1;
    if (v->right != NULL)
        v->right->rev ^= 1;
}

Node* zig(Node *v)
{
    push(v->parent);
    push(v);
    Node *u = v->parent;
    if (u->left == v)
    {
        u->left = v->right;
        if (u->left != NULL)
            u->left->parent = u;
        v->right = u;
        v->parent = u->parent;
        if (u->parent != NULL)
        {
            if (u->parent->left == u)
                u->parent->left = v;
            else
                u->parent->right = v;
        }
        u->parent = v;
    }
    else
    {
        u->right = v->left;
        if (u->right != NULL)
            u->right->parent = u;
        v->left = u;
        v->parent = u->parent;
        if (u->parent != NULL)
        {
            if (u->parent->left == u)
                u->parent->left = v;
            else
                u->parent->right = v;
        }
        u->parent = v;
    }
    return v;
}


Node* zigzig(Node *v)
{
    Node *u = v->parent;
    u = zig(u);
    v = zig(v);
    return v;
}

Node* zigzag(Node *v)
{
    v = zig(v);
    v = zig(v);
    return v;
}

Node* splay(Node *v)
{
    while (true)
    {
        if (v->parent == NULL)
            return v;
        if (v->parent->parent == NULL)
        {
            v = zig(v);
            return v;
        }
        push(v->parent->parent);
        push(v->parent);
        if (v->parent->parent->left == v->parent && v->parent->left == v)
            v = zigzig(v);
        else if (v->parent->parent->right == v->parent && v->parent->right == v)
            v = zigzig(v);
        else
            v = zigzag(v);
    }
}

Node* root(Node *u)
{
    Node *v = u;
    while (v->parent != NULL)
        v = v->parent;
    return v;
}

Node* left(Node *v)
{
    Node *u = root(v);
    push(u);
    while (u->left != NULL)
    {
        u = u->left;
        push(u);
    }
    return u;
}

Node* right(Node *v)
{
    Node *u = root(v);
    push(v);
    while (u->right != NULL)
    {
        u = u->right;
        push(u);
    }
    return u;
}

pair<Node*, Node*> split(Node *v)
{
    v = splay(v);
    push(v);
    Node *u = v->left;
    v->left = NULL;
    if (u != NULL)
        u->parent = NULL;
    return {u, v};
}

Node* merge(Node *l, Node *r)
{
    if (l == NULL)
        return r;
    if (r == NULL)
        return l;
    Node *u = right(l);
    u = splay(u);
    push(u);
    u->right = r;
    r->parent = u;
    return u;
}

Node* find1(Node *v, int key)
{
    push(v);
    if (!v)
        return NULL;
    if (v->x == key)
        return v;
    if (v->x < key)
        return find1(v->right, key);
    Node *ret = find1(v->left, key);
    if (ret == NULL)
        return v;
    return ret;
}

Node* find(Node *v, int key)
{
    return find1(root(v), key);
}


Node* findright(Node *v)
{
    return right(v);
    Node *u = root(v);
    while (u->right != NULL)
        u = u->right;
    return u;
}

Node* findleft(Node *v)
{
    return left(v);
    Node *u = root(v);
    while (u->left != NULL)
        u = u->left;
    return u;
}


pair<Node*, Node*> split(Node *v, int key)
{
    if (!v)
        return {NULL, NULL};
    Node *u = find(v, key);
    Node *r = findright(v);
    if (r->x < key)
        return {v, NULL};
    return split(u);
}


Node* insert(Node *v, int key)
{
    auto a = split(v, key);
    if (a.second != NULL && findleft(a.second)->x == key)
        return merge(a.first, a.second);
    v = merge(a.first, merge(new Node(key), a.second));
    return v;
}

void gogo(Node *v)
{
    if (!v)
        return;
    push(v);
    gogo(v->left);
    cout << v->x << ' ';
    gogo(v->right);
}

const int N = 100001;

Node* vert[N];
int pr[N];


void expose(int x)
{
    Node *v = vert[x];
    Node *last = NULL;
    while (true)
    {
        if (!v)
            return;
        Node *r = root(v);
        Node *nxt = r->link;
        r->link = NULL;
        auto a = split(v);
        if (a.first != NULL)
            a.first->link = v;
        merge(last, a.second);
        last = root(v);
        v = nxt;
    }
}

void makeRoot(int v)//not shure that it works(reverse also)
{
    expose(v);
    splay(vert[v]);
    vert[v]->rev ^= 1;
    push(vert[v]);
}

void link(int v, int u)
{
    splay(vert[v]);
    vert[v]->link = vert[u];
    pr[v] = u;
}

void cut(int v, int u)
{
    if (pr[v] != u)
        swap(v, u);
    pr[v] = v;
    expose(u);
    Node *t = root(vert[v]);
    t->link = NULL;
}

bool connected(int x, int y)
{
    expose(x);
    int fir = findright(root(vert[x]))->x;
    expose(y);
    int sec = findright(root(vert[y]))->x;
    return fir == sec;
}

int lca(int x, int y)
{
    expose(x);
    expose(y);
    if (root(vert[x])->x == root(vert[y])->x)
        return x;
    return root(vert[x])->link->x;
}

void build(int n)
{
    for (int i = 1; i <= n; i++)
        vert[i] = new Node(i);
}