RCC 2016 Round 3 - ashmelev

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <sstream>
#include <cstring>
#include <numeric>
#include <ctime>

#define re return
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) (x).size())
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define y0 y32479
#define y1 y95874
#define fill(x, y) memset(x, y, sizeof(x))
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(abs(x))
#define unq(x) (x.resize(unique(all(x)) - x.begin()))
#define spc(i,n) " \n"[i == n - 1]
#define next next239
#define prev prev239

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double LD;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

template<class T> T abs(T x) { return x > 0 ? x : -x;}

int nint() {
    int x;
    scanf("%d", &x);
    re x;
}

int m;
int n;

int dd = 400;
vi cv;

vi v[100500], nv[100500];
int ok[100500];

int ct, t1[100500], t2[100500], h[100500];

int p[100500];
int pp[20][100500];

void dfs(int x, int p) {
    if (x) {
        h[x] = h[p] + 1;
        if (ok[x])
            nv[p].pb(x);
    }

    t1[x] = ct++;
    ::p[x] = p;

    for (int y : v[x])
        dfs(y, ok[x] ? x : p);

    t2[x] = ct++;
}

int check(int x, int y) {
    re t1[x] <= t1[y] && t2[x] >= t2[y];
}

void build() {
    rep(i, n)
        pp[0][i] = p[i];
    pp[0][0] = 0;
    for (int i = 1; i <= 17; i++)
        rep(j, n)
            pp[i][j] = pp[i - 1][pp[i - 1][j]];
}

int lca(int x, int y) {
    if (check(x, y))
        re x;
    if (check(y, x))
        re y;
    for (int o = 17; o >= 0; o--) {
        int z = pp[o][x];
        if (!check(z, y))
            x = z;
    }
    re p[x];
}

void del(int x) {
    cv.pb(x);
    ok[x] = 0;

    if (sz(cv) >= dd) {
        cv.clear();
        rep(i, n)
            nv[i].clear();
        dfs(0, -1);
        rep(i, n)
            v[i] = nv[i];
        build();
    }
}

int getans(int x, int y) {
    int z = lca(x, y);
    int ans = h[x] + h[y] - 2 * h[z];
    for (int o : cv) {
        if (check(o, z))
            continue;
        if (check(o, x))
            ans--;
        if (check(o, y))
            ans--;
    }
    re ans;
}

int main() {
    cin >> n;
    rep(i, n - 1) {
        int x = nint() - 1;
        v[x].pb(i + 1);
    }
    rep(i, n)
        ok[i] = 1;

    dfs(0, -1);
    build();

    cin >> m;
    rep(i, m) {
        int t = nint();
        if (t == 1) {
            int a = nint() - 1;
            int b = nint() - 1;
            cout << getans(a, b) << "\n";
        }
        else {
            int x = nint() - 1;
            del(x);
        }
    }


    re 0;
}