Cod sursă (job #811989)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct Node {
    int ch[2], parent;
    bool rev;
    int val, sum;
};

int N;
Node tree[MAXN];
bool isRoot(int x) {
    int p = tree[x].parent;
    return (p == -1 || (tree[p].ch[0] != x && tree[p].ch[1] != x));
}

void pushUp(int x) {
    tree[x].sum = tree[x].val;
    if(tree[x].ch[0] != -1) tree[x].sum += tree[tree[x].ch[0]].sum;
    if(tree[x].ch[1] != -1) tree[x].sum += tree[tree[x].ch[1]].sum;
}

void pushDown(int x) {
    if(tree[x].rev) {
        int l = tree[x].ch[0], r = tree[x].ch[1];
        if(l != -1) {
            tree[l].rev ^= true;
            swap(tree[l].ch[0], tree[l].ch[1]);
        }
        if(r != -1) {
            tree[r].rev ^= true;
            swap(tree[r].ch[0], tree[r].ch[1]);
        }
        tree[x].rev = false;
    }
}

void rotate(int x) {
    int p = tree[x].parent, gp = tree[p].parent;
    int d = (tree[p].ch[1] == x);
    int other = tree[x].ch[d^1];
    if(!isRoot(p)) {
        if(tree[gp].ch[0] == p) tree[gp].ch[0] = x;
        else tree[gp].ch[1] = x;
    }
    tree[x].parent = gp;
    tree[p].parent = x;
    if(other != -1) tree[other].parent = p;
    tree[p].ch[d] = other;
    tree[x].ch[d^1] = p;
    pushUp(p);
    pushUp(x);
}

void splay(int x) {
    vector<int> anc;
    int cur = x;
    anc.push_back(cur);
    while(!isRoot(cur)) {
        cur = tree[cur].parent;
        anc.push_back(cur);
    }
    for (int i = anc.size()-1; i >= 0; i--)
        pushDown(anc[i]);
    while(!isRoot(x)) {
        int p = tree[x].parent, gp = tree[p].parent;
        if(!isRoot(p)) {
            if((tree[gp].ch[0] == p) ^ (tree[p].ch[0] == x))
                rotate(x);
            else
                rotate(p);
        }
        rotate(x);
    }
}
void access(int x) {
    int last = -1;
    for (int y = x; y != -1; y = tree[y].parent) {
        splay(y);
        tree[y].ch[1] = last;
        pushUp(y);
        last = y;
    }
    splay(x);
}
void makeRoot(int x) {
    access(x);
    tree[x].rev ^= true;
    swap(tree[x].ch[0], tree[x].ch[1]);
}

int findRoot(int x) {
    access(x);
    while(tree[x].ch[0] != -1) {
        pushDown(x);
        x = tree[x].ch[0];
    }
    splay(x);
    return x;
}

void link(int x, int y) {
    makeRoot(x);
    tree[x].parent = y;
}
void cut(int x) {
    access(x);
    if(tree[x].ch[0] != -1) {
        tree[tree[x].ch[0]].parent = -1;
        tree[x].ch[0] = -1;
        pushUp(x);
    }
}
int query(int x) {
    access(x);
    return tree[x].sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("dejavu.in", "r", stdin);
    freopen("dejavu.out", "w", stdout);
    int Q;
    cin >> N >> Q;
    int total = N + 1;
    for (int i = 0; i < total; i++){
        tree[i].ch[0] = tree[i].ch[1] = -1;
        tree[i].parent = -1;
        tree[i].rev = false;
        tree[i].val = (i == 0 ? 0 : 1);
        tree[i].sum = tree[i].val;
    }
    for (int i = 1; i < total; i++){
        int p;
        cin >> p;
        link(i, p);
    }

    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int x;
            cin >> x;
            int ans = query(x);
            cout << ans << "\n";
        } else {
            int x, y;
            cin >> x >> y;
            cut(x);
            link(x, y);
        }
    }
    return 0;
}