B. Мафия в КБТУ!

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

const int maxn = 202020;

typedef pair<int,int> pii;

const pii inf = make_pair(1<<30,0);

char q;
pii a[1<<20];
bool killed[maxn];
vector<int> e[maxn];
int pos[maxn<<1], parent[maxn], n, m, t, i, N, v, u;

void dfs(int v, int lvl, int pr)
{
    a[++m] = make_pair(lvl,v);
    pos[v] = m;
    parent[v] = pr;
    for (int i = 0; i < e[v].size(); i++)
    {
        int u = e[v][i];
        dfs(u, lvl + 1, v);
        a[++m] = make_pair(lvl,v);
    }
}

int lca(int u, int v)
{
    int l = pos[u];
    int r = pos[v];
    if (l > r) swap(l, r);
    pii ans = inf;
    while (l <= r)
    {
        ans = min(ans, a[l]);
        ans = min(ans, a[r]);
        l = (l + 1) >> 1;
        r = (r - 1) >> 1;
    }
    return ans.second;
}

int get_pr(int v)
{
    if (!killed[v])
        return v;
    return parent[v] = get_pr(parent[v]);
}

int main()
{
    freopen("mafia.in", "r", stdin);
    scanf("%d\n", &m);
    n = 1;
    while (m--)
    {
        q = getchar();
        if (q == '+')
        {
            scanf("%d\n", &v);
            e[v].push_back(++n);
        }
        else
        if (q == '-')
            scanf("%d\n", &v);
        else
            scanf("%d%d\n", &u, &v);
    }

    N = n+n-1;
    t = 1;
    while (t < N)
        t <<= 1;

    m = t-1;

    dfs(1,1,0);

    for (i = t+N; i < t+t; i++)
        a[i] = inf;
    for (i = t-1; i > 0; i--)
        a[i] = min(a[i<<1],a[(i<<1)+1]);

    freopen("mafia.in", "r", stdin);
    freopen("mafia.out", "w", stdout);
    scanf("%d\n", &m);
    while (m--)
    {
        q = getchar();
        if (q == '+')
            scanf("%d\n", &v);
        else
        if (q == '-')
        {
            scanf("%d\n", &v);
            killed[v] = 1;
        } else
        {
            scanf("%d%d\n", &u, &v);
            printf("%d\n", get_pr(lca(u, v)));
        }
    }
    //exit(0);
    return 0;
}