Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define INF INT_MAX/2
- #define ll long long
- #define mp make_pair
- const int MAXN = 300000 + 7;
- int t[4 * MAXN], d[4 * MAXN], a[MAXN];
- int first[MAXN], last[MAXN];
- int sz = 0;
- vector <int> g[MAXN];
- void push(int v, int l, int r) {
- t[v * 2 + 1] += d[v];
- t[v * 2 + 2] += d[v];
- d[v * 2 + 1] += d[v];
- d[v * 2 + 2] += d[v];
- d[v] = 0;
- }
- int get(int v, int l, int r, int tl, int tr) {
- if (tl >= r || tr <= l) {
- return INF;
- } else if (tl >= l && tr <= r) {
- return t[v];
- } else {
- push(v, tl, tr);
- int tm = (tl + tr) / 2;
- return min(get(v * 2 + 1, l, r, tl, tm), get(v * 2 + 2, l, r, tm, tr));
- }
- }
- void upd(int v, int l, int r, int tl, int tr, int x) {
- if (l >= r) {
- return;
- }
- if (tl >= r || tr <= l) {
- return;
- } else if (tl >= l && tr <= r) {
- t[v] += x;
- d[v] += x;
- } else {
- push(v, tl, tr);
- int tm = (tl + tr) / 2;
- upd(v * 2 + 1, l, r, tl, tm, x);
- upd(v * 2 + 2, l, r, tm, tr, x);
- t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
- }
- }
- void dfs(int v, int h) {
- first[v] = sz;
- last[v] = sz;
- a[sz] = h;
- sz++;
- for (int i = 0; i < (int) g[v].size(); i++) {
- dfs(g[v][i], h + 1);
- last[v] = sz;
- a[sz] = h;
- sz++;
- }
- }
- void build(int v, int l, int r) {
- if (r - l == 1) {
- t[v] = a[l];
- } else {
- int m = (l + r) / 2;
- build(v * 2 + 1, l, m);
- build(v * 2 + 2, m, r);
- t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int n, p, q, u, v, t;
- cin >> n;
- for (int i = 2; i <= n; i++) {
- cin >> p;
- g[p].push_back(i);
- }
- dfs(1, 0);
- build(0, 0, sz);
- cin >> q;
- while (q--) {
- cin >> t;
- if (t == 1) {
- cin >> u >> v;
- int lca = get(0, min(first[u], last[v]), max(first[u], last[v]) + 1, 0, sz);
- int h_u = get(0, first[u], first[u] + 1, 0, sz);
- int h_v = get(0, first[v], first[v] + 1, 0, sz);
- cout << h_u - lca + h_v - lca << endl;
- } else {
- cin >> v;
- upd(0, first[v] + 1, last[v], 0, sz, -1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement